Binary Tree Transformation - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

---

Implementation of Bianry Tree Transformation

• return new root
• update left/right pointer while traverse
  • root.left/right = convert(root.left, ..);
• or track prev

Example

• LeetCode 226 - Invert Binary Tree
• Sink Odd nodes in Binary Tree
  • Sink Zeros in Binary Tree
• Given a binary tree, remove all the half nodes
• Convert a given tree to its Sum Tree
• Convert a Binary Tree into its Mirror Tree
• LeetCode 669 - Trim a Binary Search Tree: Remove BST keys outside the given range

public TreeNode trimBST(TreeNode root, int L, int R) {
  if (root == null)
    return root;
  if (root.val > R)
    return trimBST(root.left, L, R);
  if (root.val < L)
    return trimBST(root.right, L, R);
  root.left = trimBST(root.left, L, R);
  root.right = trimBST(root.right, L, R);
  return root;
}

• Remove nodes on root to leaf paths of length < K
• Remove all nodes which don’t lie in any path with sum>= k

static Node pruneUtil(Node root, int k,  
                      INT sum)  
{  
    if (root == null) return null;  
    INT lsum = new INT(sum.v + (root.data));  
    INT rsum = new INT(lsum.v);  
    root.left = pruneUtil(root.left, k, lsum);  
    root.right = pruneUtil(root.right, k, rsum);  
    sum.v = max(lsum.v, rsum.v);  
    if (sum.v < k)  
    {  
        root = null;  
    }  
    return root;  
}  

public Node prune(Node root, int sum) {
    if (root == null)
        return null;
    root.left = prune(root.left, sum - root.data);
    root.right = prune(root.right, sum - root.data);
    // if node is a leaf node whose data is smaller
    // than the sum we delete the leaf.An important
    // thing to note is a non-leaf node can become
    // leaf when its children are deleted.
    if (isLeaf(root)) {
        if (sum > root.data)
            root = null;
    }
    return root;
}  

• LeetCode 156 - Binary Tree Upside Down

public TreeNode upsideDownBinaryTree(TreeNode root) {
  if (root == null) {
    return null;
  }
  return upsideDownBinaryTree(root, null);
}

private TreeNode upsideDownBinaryTree(TreeNode root, TreeNode parent) {
  if (root == null) {
    return parent;
  }
  TreeNode newNode = upsideDownBinaryTree(root.left, root);
  root.left = parent == null ? null : parent.right;
  root.right = parent;
  return newNode;
}

public TreeNode upsideDownBinaryTree(TreeNode root) {
  if (root == null || root.left == null)
    return root;
  TreeNode newRoot = upsideDownBinaryTree(root.left);
  // root.left is newRoot everytime
  root.left.left = root.right;
  root.left.right = root;
  root.left = null;
  root.right = null;
  return newRoot;
}

public TreeNode upsideDownBinaryTree(TreeNode root) {
  TreeNode p = root, parent = null, parentRight = null;
  while (p != null) {
    TreeNode left = p.left;
    TreeNode right = p.right;
    p.left = parentRight;
    p.right = parent;
    parent = p;
    parentRight = right;
    p = left;
  }
  return parent;
}

BST example

• LeetCode 538 - Convert BST to Greater Tree
  • reverse inorder traversal

  TreeNode prev;
  public TreeNode convertBST(TreeNode root) {
  if (root == null)
    return null;
  convertBST(root.right);
  root.val += prev == null ? 0 : prev.val;
  prev = root;
  convertBST(root.left);
  return root;
  }

• LeetCode 108 - Convert Sorted Array to Binary Search Tree
• LeetCode 109 - Convert Sorted List to Balanced Binary Search Tree (BST)
  • inorder: insert nodes in BST in the same order as the appear in Linked List

  private TreeNode convertListToBST(int l, int r) {
  // Invalid case
  if (l > r) {
    return null;
  }
  int mid = (l + r) / 2;
  // First step of simulated inorder traversal. Recursively form
  // the left half
  TreeNode left = this.convertListToBST(l, mid - 1);
  // Once left half is traversed, process the current node
  TreeNode node = new TreeNode(this.head.val);
  node.left = left;
  // Maintain the invariance mentioned in the algorithm
  this.head = this.head.next;
  // Recurse on the right hand side and form BST out of them
  node.right = this.convertListToBST(mid + 1, r);
  return node;
  }
  private ListNode node;
  inorderHelper(0, size - 1);
  public TreeNode inorderHelper(int start, int end){
    if(start > end){
        return null;
    }
    int mid = start + (end - start) / 2;
    TreeNode left = inorderHelper(start, mid - 1);
    TreeNode treenode = new TreeNode(node.val);
    treenode.left = left;
    node = node.next;
    TreeNode right = inorderHelper(mid + 1, end);
    treenode.right = right;
    return treenode;
  }

• LeetCode 450 - remove node from binary search tree
  • iterative version

  public TreeNode deleteNode(TreeNode root, int key) {
    if(root == null){
        return null;
    }
    if(key < root.val){
        root.left = deleteNode(root.left, key);
    }else if(key > root.val){
        root.right = deleteNode(root.right, key);
    }else{
        if(root.left == null){
            return root.right;
        }else if(root.right == null){
            return root.left;
        }
  
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, root.val);
    }
    return root;
  }

• LeetCode 776 - Split BST

public TreeNode[] splitBST(TreeNode root, int V) {
    if (root == null)
        return new TreeNode[]{null, null};
    if (root.val == V) {
        TreeNode right = root.right;
        root.right = null;
        return new TreeNode[]{root, right};
    }
    else if (root.val > V) {
        TreeNode[] nodes = splitBST(root.left, V);
        TreeNode left = nodes[0];
        TreeNode right = nodes[1];
        root.left = right;
        return new TreeNode[]{left,root};
    } else {
        TreeNode[] nodes = splitBST(root.right, V);
        TreeNode left = nodes[0];
        TreeNode right = nodes[1];
        root.right=left;
        return new TreeNode[]{root, right};
    }
}

• HARD Construct a Binary Search Tree from given postorder
  • use monotone increasing stack
  • (min, max) + recursion

  public TreeNode deserializeArrayOptimized(int[] postorder, int[] currIndex, int min, int max)
  {
  if (currIndex[0] < 0) return null;
  TreeNode root = null;
  if ((postorder[currIndex[0]] > min) && (postorder[currIndex[0]] < max))
  {
      root = new TreeNode(postorder[currIndex[0]]);
      currIndex[0] -= 1;
      root.right = deserializeArrayOptimized(postorder, currIndex, root.val, max);
      root.left = deserializeArrayOptimized(postorder, currIndex, min, root.val);
  }     
  return root;
  }
  Node constructTreeUtil(int post[], int n)
  {
    Node root = new Node(post[n - 1]);
    Stack<Node> s = new Stack<>();
    s.push(root);
    for (int i = n - 2; i >= 0; --i) {
        Node x = new Node(post[i]);
        Node temp = null;
        while (!s.isEmpty() && post[i] < s.peek().data)  
            temp = s.pop();       
        // Make x as left child of temp    
        if (temp != null)  
            temp.left = x;       
        // Else make x as right of top       
        else
            s.peek().right = x;
        s.push(x);
    }
    return root;
  }

• Construct Binary Search Tree from a given Preorder
  • (min, max) + recursion
  • monotone decreasing stack

  public int pIndex = 0;
  public Node constructTree(int[] preorder, int data, int min, int max) {
  if (pIndex < preorder.length) {
    if (preorder[pIndex] > min && preorder[pIndex] < max) {
      Node root = new Node(data);
      pIndex++;
      if (pIndex < preorder.length) {
        root.left = constructTree(preorder, preorder[pIndex], min,data);
        root.right = constructTree(preorder, preorder[pIndex],data, max);
      }
      return root;
    }
  }
  return null;
  }
  public Node constructTree(int[] preorder) {
  Stack<Node> s = new Stack<Node>();
  Node root = new Node(preorder[0]);
  s.add(root);
  for (int i = 1; i < preorder.length; i++) {
    Node x = null;
    while (!s.isEmpty() && preorder[i] > s.peek().data) {
      x = s.pop();
    }
    if (x != null) {
      x.right = new Node(preorder[i]);
      s.push(x.right);
    } else {
      s.peek().left = new Node(preorder[i]);
      s.push(s.peek().left);
    }
  }
  return root;
  }

Tree Creation/Conversion

• LeetCode 114 - Flatten Binary Tree to Linked List: pre-order
  • post-order
  • save all nodes into a list then link them

  // pre-order
  TreeNode pre;
  void flatten(TreeNode root) {
    if (root == null)
      return;
    if (pre != null) {
      pre.left = null;
      pre.right = root;
    }
    pre = root;
    TreeNode right = root.right;    
    flatten(root.left);
    flatten(right);
  }
  // post-order
  TreeNode flatten(TreeNode root) {
  if (root == null)
    return null;
  
  TreeNode leftTail = flatten(root.left);
  TreeNode rightTail = flatten(root.right);
  
  if (root.left != null) {
    TreeNode temp = root.right;
    root.right = root.left;
    root.left = null;
    leftTail.right = temp;
  }
  if (rightTail != null)
    return rightTail;
  if (leftTail != null)
    return leftTail;
  return root;
  }

• Convert a Binary Tree into Doubly Linked List in spiral fashion
• LeetCode 606 - Construct String from Binary Tree

Tree - Creation

• LeetCode 889 - Construct Binary Tree from Preorder and Postorder Traversal
  • indexMap to cache postorder
  • stack

Map<Integer, Integer> postMap = new HashMap<>();
public TreeNode constructFromPrePost(int[] pre, int[] post) {
    int length = pre.length;
    for(int i = 0; i < post.length; i++) {
        postMap.put(post[i], i);
    }
    return build(0, length - 1, 0, length - 1, pre, post);
}
private TreeNode build(int preLeft, int preRight, int postLeft, int postRight, int[] pre, int[] post) {
    if(preLeft > preRight || postLeft > postRight) {
        return null;
    }
    TreeNode root = new TreeNode(pre[preLeft]);
    if(preLeft + 1 <= preRight) {
        int index = postMap.get(pre[preLeft + 1]);
        int sum = index - postLeft;
        root.left = build(preLeft + 1, preLeft + sum + 1, postLeft, index, pre, post);
        root.right = build(preLeft + sum + 2, preRight, index + 1, postRight - 1, pre, post);
    }
    return root;
}

public TreeNode constructFromPrePost(int[] pre, int[] post) {
  Stack<TreeNode> stack = new Stack<>();
  TreeNode root = new TreeNode(pre[0]);
  stack.push(root);
  for (int i = 1, j = 0; i < pre.length; ++i) {
    TreeNode node = new TreeNode(pre[i]);
    while (stack.peek().val == post[j]) {
      stack.pop();
      j++;
    }
    if (stack.peek().left == null) {
      stack.peek().left = node;
    } else {
      stack.peek().right = node;
    }
    stack.push(node);
  }
  return root;
}

• LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal
  • indexmap to cache inorder
• Construct a tree from Inorder and Level order traversals
• LeetCode 654 - Maximum Binary Tree
  • monotone decreasing stack
  • create the TreeNode while access the data, push them into monotone stack, connect TreeNodes when push or pop

  public TreeNode constructMaximumBinaryTree(int[] nums) {
    Deque<TreeNode> stack = new LinkedList<>();
    for(int i = 0; i < nums.length; i++) {
        TreeNode curr = new TreeNode(nums[i]);
        while(!stack.isEmpty() && stack.peek().val < nums[i]) {
            curr.left = stack.pop();
        }
        if(!stack.isEmpty()) {
            stack.peek().right = curr;
        }
        stack.push(curr);
    }    
    return stack.isEmpty() ? null : stack.removeLast();
  }

• LeetCode 536 - Construct Binary Tree from String - 4(2(3)(1))(6(5))
• LeetCode 998 - Maximum Binary Tree II

Serialization

• LeetCode 572 - Subtree of Another Tree
  • Serialization or

  public boolean isSubtree(TreeNode s, TreeNode t) {
  StringBuilder sbd1 = new StringBuilder();
  StringBuilder sbd2 = new StringBuilder();
  preOrder(sbd1, s);
  preOrder(sbd2, t);
  return sbd1.toString().contains(sbd2);
  }
  private void preOrder(StringBuilder sbd, TreeNode t) {
  if(t == null) {
    sbd.append(",,");
    return;
  }     
  sbd.append(",").append(t.val);
  preOrder(sbd, t.left);
  preOrder(sbd, t.right);
  }

• LeetCode 297 - Serialize and Deserialize Binary Tree
  • pre-order
  • level order traverse

  public TreeNode deserialize(String data) {
    if (data == "") return null;
    Queue<TreeNode> q = new LinkedList<>();
    String[] values = data.split(" ");
    TreeNode root = new TreeNode(Integer.parseInt(values[0]));
    q.add(root);
    for (int i = 1; i < values.length; i++) {
        TreeNode parent = q.poll();
        if (!values[i].equals("n")) {
            TreeNode left = new TreeNode(Integer.parseInt(values[i]));
            parent.left = left;
            q.add(left);
        }
        if (!values[++i].equals("n")) {
            TreeNode right = new TreeNode(Integer.parseInt(values[i]));
            parent.right = right;
            q.add(right);
        }
    }
    return root;
  }

• LeetCode 449 - Serialize and Deserialize BST
  • pre-order + min/max
  • post-order
• LeetCode 428 - Serialize and Deserialize N-ary Tree