A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion.
Implement the CBTInserter class:
CBTInserter(TreeNode root) Initializes the data structure with the root of the complete binary tree.
int insert(int v) Inserts a TreeNode into the tree with value Node.val == val so that the tree remains complete, and returns the value of the parent of the inserted TreeNode.
TreeNode get_root() Returns the root node of the tree.
The number of nodes in the tree will be in the range [1, 1000].
0 <= Node.val <= 5000
root is a complete binary tree.
0 <= val <= 5000
At most 104 calls will be made to insert and get_root.
Solutions
Solution 1: BFS
We can use an array $tree$ to store all nodes of the complete binary tree. During initialization, we use a queue $q$ to perform level-order traversal of the given tree and store all nodes into the array $tree$.
When inserting a node, we can find the parent node $p$ of the new node through the array $tree$. Then we create a new node $node$, insert it into the array $tree$, and make $node$ as the left child or right child of $p$. Finally, we return the value of $p$.
When getting the root node, we directly return the first element of the array $tree$.
In terms of time complexity, it takes $O(n)$ time for initialization, and the time complexity for inserting a node and getting the root node are both $O(1)$. The space complexity is $O(n)$, where $n$ is the number of nodes in the tree.
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassCBTInserter:def__init__(self,root:Optional[TreeNode]):self.tree=[]q=deque([root])whileq:for_inrange(len(q)):node=q.popleft()self.tree.append(node)ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)definsert(self,val:int)->int:p=self.tree[(len(self.tree)-1)//2]node=TreeNode(val)self.tree.append(node)ifp.leftisNone:p.left=nodeelse:p.right=nodereturnp.valdefget_root(self)->Optional[TreeNode]:returnself.tree[0]# Your CBTInserter object will be instantiated and called as such:# obj = CBTInserter(root)# param_1 = obj.insert(val)# param_2 = obj.get_root()
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */typeCBTInserterstruct{tree[]*TreeNode}funcConstructor(root*TreeNode)CBTInserter{q:=[]*TreeNode{root}tree:=[]*TreeNode{}forlen(q)>0{fori:=len(q);i>0;i--{node:=q[0]q=q[1:]tree=append(tree,node)ifnode.Left!=nil{q=append(q,node.Left)}ifnode.Right!=nil{q=append(q,node.Right)}}}returnCBTInserter{tree}}func(this*CBTInserter)Insert(valint)int{p:=this.tree[(len(this.tree)-1)/2]node:=&TreeNode{val,nil,nil}this.tree=append(this.tree,node)ifp.Left==nil{p.Left=node}else{p.Right=node}returnp.Val}func(this*CBTInserter)Get_root()*TreeNode{returnthis.tree[0]}/** * Your CBTInserter object will be instantiated and called as such: * obj := Constructor(root); * param_1 := obj.Insert(val); * param_2 := obj.Get_root(); */