Problem 919

Abstract / Summary

Implement a class to insert nodes into a complete binary tree and efficiently find a parent for a new node.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0919.py

class CBTInserter:
    def __init__(self, root: Optional[TreeNode]):
        self.root  = root
        self.nodes = defaultdict(list) # all nodes, partitioned by their depth
        self.pos   = defaultdict(int)  # first node per depth which is incomplete

        def deeper(node, depth):
            if node:
                have = 0
                if node.left:
                    deeper(node.left,  depth + 1)
                    have += 1
                if node.right:
                    deeper(node.right, depth + 1)
                    have += 1

                # move single children to the left side
                if have == 1 and node.right:
                    node.left  = node.right
                    node.right = None

                self.nodes[depth].append(node)
                # skip complete nodes
                if have == 2:
                    self.pos[depth] += 1

        deeper(root, 0)

    def insert(self, val: int) -> int:
        # determine depth of the parent node
        depth = 0
        while self.pos[depth] == len(self.nodes[depth]):
            depth += 1 # skip full layers

        # create new node
        add = TreeNode(val)
        self.nodes[depth + 1].append(add)

        # and connect it to its parent
        available = self.pos[depth]
        parent    = self.nodes[depth][available]
        if parent.left:
            parent.right = add
            # parent node is complete
            self.pos[depth] += 1
        else:
            parent.left  = add

        return parent.val

    def get_root(self) -> Optional[TreeNode]:
        return self.root
52 lines | 1669 bytes | submitted December 13, 2023 | GitHub   24% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 65% (100k+ submissions).

Typical patterns to solve this problem:
  • Binary Tree
  • Breadth First Search
  • Design
  • Tree
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The class implements a helper for maintaining a complete binary tree (CBT) while supporting incremental insertions. During construction it records every node grouped by its depth and tracks, for each depth, the first node that still has a free child slot. Insertion then becomes a matter of locating that slot, attaching the new node, and updating the tracking structures. The public interface consists of three methods: the constructor, insert, and get_root.

Initialization Process

When an instance is created the constructor receives the root of an existing binary tree. It defines an inner recursive routine deeper that walks the tree depth-first, populating two dictionaries:

  • self.nodes - maps a depth integer to a list containing all nodes that appear at that depth.
  • self.pos - maps a depth integer to an index pointing at the first node in self.nodes[depth] that is incomplete (has fewer than two children).

The recursion records the presence of left and right children, counts how many children a node currently has, and performs a corrective step when a node has only a right child. In that situation the right child is promoted to the left position and the right slot is cleared, guaranteeing that any node with a single child always stores it on the left side. This invariant simplifies later insertion logic because the code can always test if parent.left: to decide whether the left slot is occupied.

def deeper(node, depth):
    if node:
        have = 0
        if node.left:
            deeper(node.left, depth + 1)
            have += 1
        if node.right:
            deeper(node.right, depth + 1)
            have += 1

        # move single children to the left side
        if have == 1 and node.right:
            node.left = node.right
            node.right = None

        self.nodes[depth].append(node)
        # skip complete nodes
        if have == 2:
            self.pos[depth] += 1

After the full traversal finishes, self.nodes contains a complete layering of the original tree, and self.pos points to the first node in each layer that still needs a child.

Insertion Logic

The insert method adds a new value while preserving the CBT property. First it determines the depth of the parent node that will receive the new child. It does this by advancing a depth counter until it finds a layer where the pointer self.pos[depth] is not equal to the length of the node list for that layer, meaning that at least one node in that layer still has a free slot.

depth = 0
while self.pos[depth] == len(self.nodes[depth]):
    depth += 1  # skip full layers

A new TreeNode is instantiated and appended to the list representing the next depth level (depth + 1).

add = TreeNode(val)
self.nodes[depth + 1].append(add)

The parent is retrieved using the stored index self.pos[depth]. If the parent already has a left child, the new node becomes the right child and the parent is now complete, so the pointer for that depth is advanced. Otherwise the new node occupies the left slot, leaving the parent still incomplete.

available = self.pos[depth]
parent = self.nodes[depth][available]
if parent.left:
    parent.right = add
    # parent node is complete
    self.pos[depth] += 1
else:
    parent.left = add

Finally the method returns the value of the parent node, matching the typical contract of a CBT inserter.

Root Retrieval

The get_root method simply returns the reference to the original root that was stored during construction. No additional computation is required.

def get_root(self) -> Optional[TreeNode]:
    return self.root

Edge Cases Handled

The implementation explicitly deals with nodes that originally have only a right child. By moving that child to the left position during initialization, the code guarantees that any node with a single child will present that child on the left side, eliminating the need for special-case checks later.

When the tree is completely filled at a certain depth, the while loop in insert automatically skips that layer, ensuring that the next insertion targets the first incomplete node in the next deeper layer.

If the supplied root is None, the dictionaries start empty; the insertion loop will immediately find depth 0 as incomplete, allowing the first inserted node to become the root’s left child once a root placeholder exists.

The use of defaultdict(int) for self.pos means that missing depth entries default to 0, which correctly represents the start of each new layer without additional initialization code.

Performance Optimizations

The design avoids repeated tree traversals on each insertion. By pre-computing a depth-wise list of nodes and maintaining a pointer to the first incomplete node per depth, the algorithm achieves constant-time identification of the insertion point.

Appending the new node to self.nodes[depth + 1] extends the layer list in amortized constant time, and updating self.pos[depth] requires only a simple increment when a node becomes complete.

The corrective step that normalizes single-child nodes to the left side occurs once during construction, preventing the need for conditional logic during every insertion.

Overall, the data structures (lists indexed by depth and integer pointers) provide direct access patterns that keep the runtime per operation minimal and the memory layout compact, as each node is stored exactly once in the appropriate depth list.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a giant family tree that grows from the top down. The code sets up a special librarian whose job is to keep track of every person in the tree and make sure they have a place to sit.

The librarian starts by looking at the whole tree. They walk through every branch to see who is already there, organizing people by how far down they are from the very top. If someone is sitting in the wrong spot or only has one friend waiting underneath them, the librarian moves things around so that everyone is in a neat row.

When a brand-new person wants to join the tree, the librarian checks their list to find the first spot where someone is waiting for a friend. Once they find that empty space near the bottom, they add the new person and connect them to their new family member. The librarian then keeps a note that this part of the tree is now full so they can find the next perfect spot for the next person who arrives.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 6.19 | σ = 1.42

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ JS Python Java Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
everthis JS
fartem Ruby
fsq C++
JoshCrozier JS
lzl124631x C++
suxrobGM C#
trung-hn Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fartem Ruby
fsq C++
JoshCrozier JavaScript
lzl124631x C++
suxrobGM C#
trung-hn Python
28 links | 14 authors | 8 languages

Videos

1 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

10 solutions   December 13, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality