Summary of Binary Tree: (Build)

interview

---

• Summary of Binary Tree: (Build)
  • • 0. Definitions of Binary Tree Node and Segment Tree Node
    • 1. Convert Sorted Array to BST
    • 2. Convert Sorted Linked List to BST
    • 3. Flatten Binary Tree to Linked List
    • 4. Construct Binary Tree from Preorder and Inorder Traversal
    • 5. Unique Binary Trees II
    • 6. Max Tree
    • 7. Segment Tree

0. Definitions of Binary Tree Node and Segment Tree Node

public class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode(int i) {
        val = i;
        left = right = null;
    }
}
public class SegmentTreeNode{
    int start, end, count;
    SegmentTreeNode left, right;
    SegmentTreeNode(int start, int end){
        this.start = start;
        this.end = end;
        left = right = null;
    }
}

1. Convert Sorted Array to BST

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Example : 1,3,5,6,7,8,9

         6
        / \
      3     8
     / \   / \
    1   5 7   9

Idea:
Each time pick the middle element in the array, make it as the root:
1. its left child is the middle element of the left subarray
2. its right child is the middle element of the right subarray

public TreeNode build(int[] nums, int low, int high){
    if(low>high) return null;
    int mid = (low+high)/2;
    int val = nums[mid];
    TreeNode root = new TreeNode(val);
    root.left = build(nums, low, mid-1);
    root.right = build(nums, mid+1, high);
    return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
    int n = nums.length;
    if(n==0) return null;
    return build(nums, 0, n-1);
}

2. Convert Sorted Linked List to BST

Given a singly linked list where elements are s orted in ascending order, convert it to a height balanced BST.

Example : 1->3->5->6->7->null

        5
       / \
      3   6
     /     \
    1       7

Idea: Create Root with Bottom-up Recursion
KEY: make list head global (if Cpp, just pass by a reference to the head pointer)
1. Make left child node using the middle of left half list
2. Make root node using the middle of list
3. Make right child node using the middle of the right half list

public int getListLength(ListNode head){
    if(head==null) return 0;
    return 1+getListLength(head.next);
}
public ListNode curhead; // important! 
public TreeNode build(int len){
    if(curhead==null || len<=0) return null;
    TreeNode left = build(len/2);
    TreeNode root = new TreeNode(curhead.val);
    root.left = left;
    curhead = curhead.next;
    TreeNode right = build(len-len/2-1);
    root.right = right;
    return root;
}
public TreeNode sortedListToBST(ListNode head) {
    int len = getListLength(head);
    curhead = head; 
    return build(len);
}   

3. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

Example:

         1
        / \
       2   5
          /    
         6

Output

   1
    \
     2
      \
       5
        \
         6

Idea:
For each node
1. flatten right subtree to list
2. flatten left subtree

if left subtree is null, then just return the root
else 
    1) append the flattened right subtree to the *tail* of flattened left subtree
    2) attach to the right child of the node while set the left child of the node to null    

public TreeNode build(TreeNode node){
    if(node==null) return null;
    TreeNode right = build(node.right);
    TreeNode left = build(node.left);
    if(left != null){
        TreeNode left_tail = left;
        while(left_tail !=null && left_tail.right!=null){
            left_tail = left_tail.right;
        }
        left_tail.right = right;
        node.left = null;
        node.right = left;
    }
    return node;
}
public void flatten(TreeNode root){
    root = build(root);
}

4. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Example: Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

  2
 / \
1   3

Idea:
1. Locate the root: for the sequence from preorder traversal, the root always shows at the first
2. Split the inorder sequence into two halves: left subtree and right subtree
3. For each subtree sequence, we can tell the size of subtree
4. Use the determined subtree size in the preorder sequence (exclude the root), find the left subtree root and the right subtree root, and repeat from step 1

public TreeNode build(int[] preorder, int[] inorder, int prestart, int preend, int instart, int inend, HashMap<Integer, Integer> inorder_pos){
    if(prestart>preend || instart>inend) return null;
    int val = preorder[prestart];
    TreeNode root = new TreeNode(val);
    int pos = inorder_pos.get(val);
    int leftsize = pos-instart;
    int rightsize = inend-pos;
    root.left = build(preorder, inorder, prestart+1, prestart+leftsize, instart, pos-1, inorder_pos); 
    root.right = build(preorder, inorder, preend-rightsize+1, preend, pos+1, inend, inorder_pos);
    return root;
}
public TreeNode buildTree(int[] preorder, int []  inorder){
    int n = preorder.length;
    if(n==0) return null;
    HashMap<Integer, Integer> inorder_pos = new HashMap<Integer, Integer>();
    for(int i=0; i<n; i++){
        inorder_pos.put(inorder[i],i);
    }   
    return build(preorder, inorder, 0, n-1, 0, n-1, inorder_pos);
}

5. Unique Binary Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

Example: Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Idea:
Given a number $n$, for each $i \in [1, n]$, it can be a tree root. For a root with value $i$:
1. its left subtree node could be any number $j \in [1, i-1]$ ($i-1$ possible choices)
2. its right subtree node could be any number $k \in [i+1, n]$ ($n-i$ possible choices)
Note as we increase variable $i$, we need a terminate condition: when $i<1$ or $i>n$, let it corresponds to a null node.

Using bottom-up construction, for node $i$:
construct a set ($L$) of all possible nodes belonging to its left subtree,
construct a set ($R$) of all possible nodes belonging to its right subtree,
that is, if we choose a node $a \in L$ as the left child of node $i$, then, we have $R.size()$ choices to select a right child for the node $i$

public void build(List<TreeNode> roots, int start, int end){
    if(start>end){ 
        roots.add(null);
        return;
    }
    for(int i=start; i<=end; i++){ // Note: not from 1 to n
        List<TreeNode> L = new ArrayList<TreeNode>();
        build(L, start, i-1);
        List<TreeNode> R = new ArrayList<TreeNode>();
        build(R, i+1, end);
        for(TreeNode a : L){
            for(TreeNode b : R){
                TreeNode root = new TreeNode(i);
                root.left = a;
                root.right = b;
                roots.add(root);
            }
        }
    }
}
public List<TreeNode> generateTrees(int n) {
    List<TreeNode> res = new ArrayList<TreeNode>();
    build(res, 1, n); // Note: start from 1 not 0
    return res;
}   

6. Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

The root is the maximum number in the array
The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.

Example : [2, 5, 6, 0, 3, 1]

          6
        /   \
       5     3
      /     /  \
     2     0    1

Idea:
Sequentially create tree node when iterate the input array (one-pass)
KEY: maintaining/updating the root node: $R$
For $i$ in the array, create a node $n_i$
1. if $R$ is null, make $n_i$ the root
2. if $n_i$ value is greater than the root's value, then make $n_i$ the root, attach previous root as its left subtree
3. otherwise, insert $n_i$ to a proper position in current root's right subtree, by recursively executing step 1 to 3 with $R.right$ as root

public TreeNode insert(TreeNode root, int cur){
    TreeNode node = new TreeNode(cur);
    if(root==null) {
        return node;
    }
    if(node.val>root.val){
        node.left = root;
        return node;
    }
    // keep on looking up the right subtree of root and update the right child
    root.right = insert(root.right, cur);    
    return root; 
}
public TreeNode maxTree(int[] A) {
    int n = A.length;
    if(n==0) return null;
    TreeNode root = new TreeNode(A[0]);
    for(int i=1; i<n; i++){
        int cur = A[i];
        if(cur > root.val){
            TreeNode node = new TreeNode(cur);
            node.left = root;
            root = node;
        }else{
            root.right = insert(root.right, cur);
        }
    }
    return root;
}

7. Segment Tree

The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment/interval.

start and end are both integers, they should be assigned in following rules:

The root's start and end is given by build method.
The left child of node A has start=A.start, end=(A.start + A.end) / 2.
The right child of node A has start=(A.start + A.end) / 2 + 1, end=A.end.
if start equals to end, there will be no children for this node.

Implement a build method with two parameters start and end, so that we can create a corresponding segment tree with every node has the correct start and end value, return the root of this segment tree.

Exmaple : Given start = 0, end = 4

            [0, 4] 
          /        \
      [0,2]         [3,4]
     /     \       /     \
   [0,1]  [2,2]  [3,3]   [4,4]
  /   \
[0,0][1,1]

// Recurisve version
public SegmentTreeNode build(int start, int end){
    if(start > end) return null;
    SegmentTreeNode root = new SegmentTreeNode(start, end);
    if(start == end) return root;
    int mid = (start+end)/2;
    root.left = build(start, mid);
    root.right= build(mid+1, end);
    return root;
}
// Iterative version
public SegmentTreeNode build(int start, int end) {
    if(start > end) return null;
    SegmentTreeNode root = new SegmentTreeNode(start, end);
    if(start == end) return root;
    Queue<SegmentTreeNode> Q = new LinkedList<SegmentTreeNode>();
    Q.add(root);
    while(!Q.isEmpty()){
        SegmentTreeNode cur = Q.poll();
        if(cur.start != cur.end){
            SegmentTreeNode left = new SegmentTreeNode(cur.start, (cur.start+cur.end)/2);
            cur.left = left;
            SegmentTreeNode right = new SegmentTreeNode((cur.start+cur.end)/2+1, cur.end);
            cur.right = right;
            Q.add(cur.left);
            Q.add(cur.right);
        }
    }
    return root;
}