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
Difficulty
and has an acceptance rate of about 65% (100k+ submissions).
Typical patterns to solve this problem:
- Binary Tree
- Breadth First Search
- Design
- Tree
AI Disclaimer
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.
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 inself.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.
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.
Code Quality
Complexity Analysis
Other Solutions
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 |
Videos
Solved On The Same Day
- problem 1022: Sum of Root To Leaf Binary Numbers
- problem 1582: Special Positions in a Binary Matrix
- problem 2331: Evaluate Boolean Binary Tree
- problem 449: Serialize and Deserialize BST
- problem 894: All Possible Full Binary Trees
- problem 951: Flip Equivalent Binary Trees
- problem 2415: Reverse Odd Levels of Binary Tree
- problem 297: Serialize and Deserialize Binary Tree
- problem 834: Sum of Distances in Tree
Extra
- 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