Leetcode: Complete Binary Tree Inserter

Complete Binary Tree Inserter



Similar Problems:


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.

Write a data structure CBTInserter that is initialized with a complete binary tree and supports the following operations:

CBTInserter(TreeNode root) initializes the data structure on a given tree with head node root;
CBTInserter.insert(int v) will insert a TreeNode into the tree with value node.val = v so that the tree remains complete, and returns the value of the parent of the inserted TreeNode;
CBTInserter.get_root() will return the head node of the tree.

Example 1:

Input: inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
Output: [null,1,[1,2]]

Example 2:

Input: inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
Output: [null,3,4,[1,2,3,4,5,6,7,8]]

Note:

  1. The initial given tree is complete and contains between 1 and 1000 nodes.
  2. CBTInserter.insert is called at most 10000 times per test case.
  3. Every value of a given or inserted node is between 0 and 5000.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/complete-binary-tree-inserter
// Basic Ideas: track the second last row
// Complexity: Time O(n), Space O(n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 * Val int
 * Left *TreeNode
 * Right *TreeNode
 * }
 */
type CBTInserter struct {
    root *TreeNode
    nodes []*TreeNode
    index int
}

func Constructor(root *TreeNode) CBTInserter {
    res := CBTInserter{root, []*TreeNode{}, 0}
    if root.Left == nil {
        res.nodes = []*TreeNode{root}
    } else {
                p := root
                for p.Left != nil && p.Left.Left != nil {
                        p = p.Left
                }
                // BFS
                queue := []*TreeNode{root}
                for len(queue) != 0 {
                        if queue[0] == p {
                                res.nodes = queue
                                for _, node := range queue {
                                        if node.Left != nil { res.index++ }
                                        if node.Right != nil { res.index++ }
                                }
                                break
                        }
                        l := []*TreeNode{}
                        for _, node := range queue {
                                if node.Left != nil { l = append(l, node.Left) }
                                if node.Right != nil { l = append(l, node.Right) }
                        }
                        queue = l
                }
    }
    return res
}

func (this *CBTInserter) Insert(v int) int {
    newNode := &TreeNode{v, nil, nil}
    res := 0
    // current level is full
    if this.index == 2*len(this.nodes) {
        l := []*TreeNode{}
        for _, p := range this.nodes {
            l = append(l, p.Left)
            l = append(l, p.Right)
        }
        this.nodes, this.index = l, 1
        this.nodes[0].Left = newNode
        res = this.nodes[0].Val
    } else {
        p := this.nodes[this.index/2]
        if this.index % 2 == 0 {
            p.Left = newNode
        } else {
            p.Right = newNode
        }
        this.index++
        res = p.Val
    }
    return res
}

func (this *CBTInserter) Get_root() *TreeNode {
    return this.root
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Insert(v);
 * param_2 := obj.Get_root();
 */
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.