Insert Into Complete Binary Tree (Level-Order)#
Practice Link#
Description#
- Inferred from your notes: “insert/attach child”, BFS levels, left-to-right.
- Given the root of a binary tree and a value
val, insert a new node such that the tree remains a complete binary
tree:
- fill levels top-to-bottom
- and within a level, fill left-to-right
- Concretely: perform level-order traversal and insert at the first node missing a left child, else the first node
missing a right child.
- Return the root.
Examples#
1Input: root = [1,2,3,4,5,6], val = 7
2Output: [1,2,3,4,5,6,7]
1Input: root = [1,2,3,4,5,6], val = 8
2Output: [1,2,3,4,5,6,7,8]
Python Solution#
1from collections import deque
2from typing import Optional
3
4
5class TreeNode:
6 def __init__(self, val: int = 0,
7 left: Optional["TreeNode"] = None,
8 right: Optional["TreeNode"] = None):
9 self.val = val
10 self.left = left
11 self.right = right
12
13def insert_complete(root: Optional[TreeNode], val: int) -> TreeNode:
14 """
15 Insert `val` into the first available spot to maintain completeness.
16
17 Time: O(n) worst-case per insertion
18 Space: O(width of tree) due to queue
19 """
20 new_node = TreeNode(val)
21 if root is None:
22 return new_node
23
24 q = deque([root])
25 while q:
26 node = q.popleft()
27
28 if node.left is None:
29 node.left = new_node
30 return root
31 else:
32 q.append(node.left)
33
34 if node.right is None:
35 node.right = new_node
36 return root
37 else:
38 q.append(node.right)
39
40 return root # logically unreachable