Back to top

Binary Trees

Overview

In the subsequent sections, we will be providing different patterns of programming questions commonly asked in coding interviews which can be solved using binary tree. We don’t want to overwhelm our readers with a plethora of binary tree questions. So, we have done the heavy lifting for you by going through almost all the questions on leetcode and categorizing the different patterns of questions commonly asked in the interviews.

Pattern 1: Breadth-First Search Based

Prob 1302: Deepest Leaves Sum

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to find the sum of the deepest leaves in a tree.
         * https://leetcode.com/problems/deepest-leaves-sum/
         *
         *
         * Approach: We used the approach of breadth first search to
         * find the deepest-level leaves and find the sum of those
         * elements.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         */
        public int deepestLeavesSum(TreeNode root) {
            if (root == null) {
                return 0;
            }

            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int sum = 0;
            while (!queue.isEmpty()) {
                int curSize = queue.size();
                sum = 0;
                while (curSize-- > 0 && !queue.isEmpty()) {
                    TreeNode node = queue.poll();
                    sum += node.val;
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
            }
            return sum;
        }

Pattern 2: Depth First Search Based

Prob 124: Binary Tree Max Path Sum

NOTE: We recommend you to solve the problem at your end before reading further.

**Solution:**
    public class BinaryTreeMaxPathSum {

        int max_sum;

        /**
         * We need to find the maximum path sum where a path is defined
         * as any sequence of nodes and doesn't need to go through root.
         * https://leetcode.com/problems/binary-tree-maximum-path-sum/
         *
         * Approach: We want to calculate the sum of path originating from
         * left or right child of a node in a recursive manner. We then include
         * the value of the node to check if the resulting sum exceeds the sum of
         * value encountered so far. We then return the sum of the node's value and
         * the larger of the path originating from the left and right node.
         *
         * Time Complexity:O(n)
         * Space Complexity: O(1)
         *
         * @param root
         * @return
         */
        public int maxPathSum(TreeNode root) {
            max_sum = Integer.MIN_VALUE;
            max_gain(root);
            return max_sum;
        }

        int max_gain(TreeNode root){
            if(root == null){
                return 0;
            }

            int leftGain = Math.max(max_gain(root.left), 0);
            int rightGain = Math.max(max_gain(root.right), 0);
            int sum = root.val + leftGain + rightGain;
            max_sum = Math.max(max_sum, sum);
            return root.val + Math.max(leftGain, rightGain);
        }
    }

Prob 236: Lowest Common Ancestor

NOTE: We recommend you to solve the problem at your end before reading further.

**Solution:**
       /**
         * We need to find the lowest common ancestor in a tree of two nodes.
         * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
         *
         * Approach: We take the bottom-up approach where we check the left and right
         * children of a node. If the nodes we are looking for exists in the left and
         * the right child path of a node then that node becomes the lowest common ancestor.
         * Otherwise, we return the non-empty left or the right node.
         *
         * Time Complexity:O(n)
         * Space Complexity: O(1)
         *
         * @param root
         * @param p
         * @param q
         * @return
         */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null)
                return null;
            if (root == p || root == q) {
                return root;
            }
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            if (l != null && r != null) {
                return root;
            } else if (l != null) {
                return l;
            } else {
                return r;
            }
        }

Prob 337: House Robber III

NOTE: We recommend you to solve the problem at your end before reading further.

**Solution:**
       /**
         * We need to find the maximum amount of money the
         * thief can rob without alerting police.
         * https://leetcode.com/problems/house-robber-iii/
         *
         * Approach: We use a map to store the amount of money
         * the robber would have stolen at every given node using
         * a bottom-up model. At every node, there are two options
         * either the robber robs a node and it's grand-children or
         * the node's children. We then update this value in the map.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         *
         * @param root
         * @return
         */
        Map<TreeNode, Integer> map = new HashMap<>();
        public int rob(TreeNode root) {

            if(root == null)
                return 0;

            return getVal(root);
        }

        public int getVal(TreeNode root){

            if(root == null)
                return 0;

            if(map.containsKey(root)) {
                return map.get(root);
            }

            //If the node is being robbed
            int nodeRobVal = root.val;

            if(root.left != null){
                nodeRobVal +=  getVal(root.left.left) + getVal(root.left.right);
            }

            if(root.right != null){
                nodeRobVal += getVal(root.right.right) + getVal(root.right.left);
            }

            //return the value in both the possible scenarios
            int ret = Math.max(nodeRobVal, getVal(root.left) + getVal(root.right));
            map.put(root, ret);
            return ret;
        }

Pattern 3: Search-Based

Prob 230: Kth Smallest Element

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to find the kth smallest element in a BST.
         * https://leetcode.com/problems/kth-smallest-element-in-a-bst/
         *
         * Approach: We use a pre-order traversal approach where we first
         * check the number of elements in the left sub-tree. If the number
         * of nodes is more than "k" then we move to the left sub-tree. Otherwise,
         * we move to the right sub-tree.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(1)
         *
         */
        public int kthSmallest(TreeNode root, int k) {
            if (root == null) {
                return 0;
            }

            int leftCount = count(root.left);

            if (k <= leftCount) {
                return kthSmallest(root.left, k);
            } else if(k == leftCount + 1) {
                return root.val;
            } else {
                return kthSmallest(root.right, k - leftCount -1);
            }
        }

        int count(TreeNode node) {
              if(node == null) {
                  return 0;
              }
              return count(node.left) + count(node.right) + 1;
        }

Pattern 4: Serialization-Based

Prob 297: Serialize and De-serialize Binary Tree

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We design an algorithm to serialize a binary tree.
         * https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
         *
         * Approach: We serialize the tree by using pre-order traversal. We append
         * the value of the nodes in a string buffer. We use a string character "n"
         * for empty nodes and append a blank space after every node.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         */
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);

            while (!queue.isEmpty()) {
                TreeNode curr = queue.poll();
                if (curr == null) sb.append("n ");
                else {
                    sb.append(curr.val).append(" ");
                    queue.add(curr.left);
                    queue.add(curr.right);
                }
            }

            return sb.toString().trim();
        }

        /**
         * We design an algorithm to deserialize a binary tree.
         * https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
         *
         * Approach: We deserialize the tree by splitting the string with the space
         * character : " " to create an array. After that, we iterate through the
         * array by using an index to create the left and the right children of the
         * node.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         */
        public TreeNode deserialize(String data) {
            String[] parts = data.split(" ");
            int index = 0;
            TreeNode root = getNode(parts[index++]);
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);

            while (!queue.isEmpty()) {

                TreeNode curr = queue.poll();
                if (curr != null) {

                    curr.left = getNode(parts[index++]);
                    curr.right = getNode(parts[index++]);

                    queue.add(curr.left);
                    queue.add(curr.right);
                }
            }

            return root;
        }

        private TreeNode getNode(String p) {
            if (p.equals("n")) return null;
            return new TreeNode(Integer.parseInt(p));
        }

Prob 105: Binary Tree from pre-order and in-order traversals

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /**
         *
         * We have to construct a binary tree from a pre-order and in-order traversal.
         * https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
         *
         * Approach: We build a tree by splitting the pre-order and in-order traversal arrays
         * in two separate halves. The left and right halves of the inorder array will be split to
         * create the left and right sub-trees respectively. The pre-order array for the left sub-tree
         * will increment by 1 and for the right by the number of elements the preOrder val is ahead of
         * the start of the in-order sub-array.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(1)
         */
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTree(preorder, inorder, 0, 0, inorder.length - 1);
        }

        private TreeNode buildTree(int[] preorder, int[] inorder, int pre, int l, int r) {
            if (r < l) return null;
            // in and pre are the indexes of root on inorder and preorder.
            int in, val = preorder[pre];
            for(in = l; in <= r; in++)
                if (inorder[in] == val) break; // seek position of in

            // left subtree root is next preorder head, take left chunk of inorder
            // right subtree root in preorder is after left subtree size, take right chunk of inorder
            return new TreeNode(val,
                    buildTree(preorder, inorder, pre + 1, l, in - 1),
                    buildTree(preorder, inorder, pre + 1 + in - l, in + 1, r)
            );
        }