Binary tree pattern

Find a path for the target in the binary tree

1. Let the method return true/false in the given current subtree.
2. Add current as a possible answer in the path array.
3. If the current is the target then return true
4. If the target is found in either the left or right subtree then return true.
5. Otherwise, remove a current from the path.

Following is the code to implement this logic.

const hasPath = (root, target) => {
    const ans = [];
    const dfs = node => {
        // base case: null node
        if (!node) {
            return false;
        }
        // Capture node in path
        ans.push(node);
        // if match then return
        if (node.val === target.val) {
            return true;
        }
        // if node is found in either left or right subtree then return true
        if (dfs(node.left) || dfs(node.right)) {
            return true;
        }
        // not found in either left or right then remove from path
        ans.pop();
        return false;
    }
    dfs(root);
    return ans;
}

Build tree from inorder and preorder traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Hash-based approach

1. The first node of preorder is the root of the tree.
2. How do we discover the left and right subtree of the discovered root node?
3. We can leverage the given inorder traversal. if we find the position of the root in the inorder traversal then all the nodes to the left will be the left subtree and all the nodes to the right will be the right subtree.
4. We can count how many nodes are in the left subtree and how many are in the right subtree.
5. We can use this count in the preorder traversal to find out the range for the left and right subtree.
6. Then we divide the preorder traversal problem into left and right subtrees and corresponding inorder subtrees.
7. Run the same approach on each left and the right subtree.

Where to use hash here?

To search the root node in the given inorder traversal, instead of liner scan, we can store the index position in the hash map for constant query time.

Following is the code to implement it using a hashmap.

var buildTree = function (preorder, inorder) {
    // build inorder mapping
    const inorderMap = inorder.reduce((map, item, i) => { map.set(item, i); return map }, new Map());
    const constructTree = (pStart, pEnd, iStart, iEnd) => {
        if (pStart > pEnd || iStart > iEnd) {
            return null;
        }
        // first element of preorder will be root
        const val = preorder[pStart];
        const node = new TreeNode(val);

        // get index in inorder
        const breakPoint = inorderMap.get(val);
        const lSize = breakPoint - iStart;
        const rSize = iEnd - breakPoint;

        node.left = constructTree(pStart + 1, pStart + lSize, iStart, breakPoint - 1);
        node.right = constructTree(pStart + lSize + 1, pEnd, breakPoint + 1, iEnd);
        return node;
    }
    return constructTree(0, preorder.length - 1, 0, inorder.length - 1)
};

Time complexity: O(n) with the assumption that the hash read is O(1) . If consider the worst case of hash read then it would be O(n) which will lead to O(n*n) for the build tree method.

Space complexity: O(n)

Stack-based approach

This is a very complicated approach and therefore not discussed here.

Verify a binary tree is a binary search tree

https://leetcode.com/problems/validate-binary-search-tree/description/

Properties of binary search tree

1. The left child (subtree) contains values less than the parent node.
2. The right child (subtree) contains values greater than the parent node.

Approach 1: Verify the min & max from both the left and right subtree

Based on the above properties we can take the following approach

1. For each node, find out the min and max value in its left subtree.
2. Similarly, find out the min and max value in its right subtree.
3. The node value should be higher than max from the left subtree.
4. The node value should be less than the min from the right subtree.
5. Since the node needs to wait for results from both the left and right subtree, therefore, this would be post-order traversal.
6. Since dfs() is returning {min, max} i.e. it is not returning ans therefore we need to maintain the global flag and set it to false if any condition didn’t match.

Following is the implementation of this approach.

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
    let isValid = true;

    const dfs = (node) => { // return {min, max} for each node
        // base case: null node
        if (!node) {
            return [Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER];
        }
        const [lMin, lMax] = dfs(node.left);
        const [rMin, rMax] = dfs(node.right);

        // Verify BST structure
        const value = node.val;
        if (value >= rMin || value <= lMax) {
            isValid = false;
        }
        // Calculate overall new min & max
        return [Math.min(lMin, value), Math.max(rMax, value)];
    }
    dfs(root);
    return isValid;
};

Note: We can check for isValid in the beginning and do pruning if it is already set as false .

Approach 2: Find out the predecessor and successor for each node and verify the order

Verify if a binary tree is balanced search binary tree

We can split verification into two steps.

1. Verify if a binary tree is a binary search tree using the steps discussed above.
2. Verify if a binary search tree is balanced or not.

https://leetcode.com/problems/balanced-binary-tree/description/

To check whether a tree is height-balanced or not, we can take the following approach.

1. For each node, get the height for the left node.
2. Similarly, find the height for the second node.
3. The height difference between left and right should be one.
4. Since the node needs to wait for both left and right child therefore need to apply postorder traversal.
5. Also, dfs(node) return the height therefore need to maintain the global flag to determine the answer.

Following is the code to implement this logic.

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
    let valid = true;
    const dfs = (node) => {
        // Base case: empty node has height 0
        if (!node) {
            return 0;
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
        if (Math.abs(left - right) > 1) {
            valid = false;
        }
        return 1 + Math.max(left, right);
    }
    dfs(root);
    return valid;
};

Note: We can check for isValid in the beginning and do pruning if it is already set as false .

Constructor balanced binary search tree from given sorted array

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

Following is the intuition to construct the BBST.

1. Find out the middle element of the array and make it the root node of the tree.
2. Then perform the same operation on the left subarray for the root’s left child.
3. Similarly, perform the same operation on the right subarray for the root’s right child.

Following is the code to implement this approach.

var sortedArrayToBST = function (nums) {
    const recursion = (left, right) => {
        // Base case: empty array
        if (left > right) {
            return null;
        }
        // Find the middle
        const mid = left + Math.floor((right - left) / 2);
        const root = new TreeNode(nums[mid]);
        root.left = recursion(left, mid - 1);
        root.right = recursion(mid + 1, right);
        return root;
    }
    return recursion(0, nums.length - 1);
};

Balance a binary search tree

https://leetcode.com/problems/balance-a-binary-search-tree/description/

Given the root of a binary search tree, return a balanced binary search tree with the same node values.

Approach 1: In order traversal followed by construction

1. Apply inorder traversal to find out the sorted array.
2. Then construct a balanced binary search tree from the sorted array.

Approach 2: Day-Stout-Warren algorithm

1. Convert the given BST into a linked list ( right-sided linked list ) using the concept of right rotations by means of inorder traversal. This form of BST is known as backbone or vine.
2. Calculate the height of BST in which all the levels will be completely filled using the formula h = log2(N+1) [N is the total number of nodes].
3. Using the height calculate the number of nodes that can be fitted in that height m = pow(2, h)-1. [h is the height till which all the levels are fully filled with nodes]

Binary tree to doubly linked list conversion

Given a Binary Tree, The task is to convert it to a Doubly Linked List keeping the same order.

1. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL.
2. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree.
3. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.

The above binary tree should be converted in place into a doubly linked list as below.

Following is the approach to perform this conversion.

1. Perform inorder traversal of the tree.
2. Keep track of the previously visited node.
3. For every visited node, make it next to the previous one and vice versa.
4. Initialize head variable only when prev is null.

Following is the code to implement it.

const convertTreeIntoDoublyLinkedList = root => {
  let head;
  let prev;
  const dfs = (node, prev) => { // Inorder dfs
    // Base case
    if(!node) {
      return;
    }
    dfs(node.left, node);
    // Process node here ie. update pointers
    if(!prev) { 
      head = node; // First time initialize the head
      node.left = prev;
    } else {
      node.left = prev;
      prev.right = node;
    }
    
    dfs(node.right, node);
  }
  dfs(root, null);
  return head;
}

Sort a doubly linked list

Below is a simple insertion sort algorithm for doubly-linked lists.
1) Create an empty sorted (or result) doubly linked list.
2) Traverse the given doubly linked list, and do the following for every node.
a) Insert the current node in a sorted way in the sorted(or result) doubly linked list.
3) Change the head of the given linked list to the head of the sorted (or result) list.

Sorted Linked List to Balanced BST

1. Given a Singly Linked List which has data members sorted in ascending order.
2. Construct a Balanced Binary Search Tree that has the same data members as the given Linked List.

Approach 1: Similar to a sorted array i.e. find middle and use it as the root

1. Get the Middle of the linked list and make it root.
2. Recursively do the same for the left half and right half.
   a) Get the middle of the left half and make it the left child of the root
   created in step 1.
   b) Get the middle of the right half and make it the right child of the
   root created in step 1.

Time complexity: o(nlogn)

Approach 2: Construct from leaf to root

1. The idea is to insert nodes in BST in the same order as they appear in the Linked List so that the tree can be constructed in O(n) time complexity.
2. We first count the number of nodes in the given Linked List.
3. Let the count be n.
4. After counting nodes, we take left n/2 nodes and recursively construct the left subtree.
5. After the left subtree is constructed, we allocate memory for the root and link the left subtree with the root.
6. Finally, we recursively construct the right subtree and link it with the root.
7. While constructing the BST, we also keep moving the list head pointer to the next so that we have the appropriate pointer in each recursive call.

Convert doubly linked list into a balanced binary search tree

1. Given a Doubly Linked List which has data members sorted in ascending order.
2. Construct a Balanced Binary Search Tree that has the same data members as the given Doubly Linked List.
3. The tree must be constructed in place (No new node should be allocated for tree conversion)

Approach would be same as single linked list problem.

Binary search conversion

Morris order traversal

Goal

1. Find inorder traversal with O(1) extra space.
2. Please note; that the recursion takes O(h) space as recursion stack size.

Approach: Based on marking the link

1. Build a link for the node’s inorder successor.
2. For each node, check if it has left a marking link, then switch off, process the node, and move to the right. If inactive then switch it on and move to left.
3. If node has no left then process the node and go right.

Following is the code to implement this traversal.

var inorderTraversal = function(root) {
    const ans = [];
    let node = root;
    while(node) {
      // explore left subtree
      if(node.left){
        // traverse right nodes or if same as curr then skip
        let temp  = node.left;
        while(temp.right !== null && temp.right !== node) {
            temp = temp.right;
        }
        // Verify the marking link
        if(temp.right === node) { // link is active
            temp.right = null; // mark it off
            ans.push(node.val); // process node
            node = node.right; // explore right subtree
        } else { // link is not active
            // Note: For pre-order traversal, we can process it here
            temp.right = node; // mark link active
            node = node.left; // keep exploring left subtree
        }
      } else {
        ans.push(node.val); // process node
        node = node.right; // explore right subtree
      }  
    }
    return ans;
};

Note: To traverse from right to left we can change the marking to use left pointer. This is helpful to find out the kth the largest node in BST.

Flip a binary tree

https://leetcode.com/problems/invert-binary-tree/

1. Apply preorder traversal
2. For each node swap the left and right nodes.

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
    const dfs = node => {
        if (!node) {
            return;
        }
        // Swap left & right node
        [node.left, node.right] = [node.right, node.left];
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return root;
};

K sum path

Variation #1: Number of paths starting from the root to leaf with sum K

https://leetcode.com/problems/path-sum-ii/description/

var pathSum = function(root, targetSum) {
    if(!root) {
        return [];
    }
    const ans = [];
    const dfs = (node, total, path) => {
        const sum = total + node.val;
        path.push(node.val);
        // base case: leaf node
        if(!node.left && !node.right) {
            if(sum === targetSum) {
                ans.push([...path]);
            }
            // remove node from path for rest of discovery
            path.pop();            
            return;
        }
        if(node.left) {
            dfs(node.left, sum, path);
        }
        if(node.right) {
            dfs(node.right, sum, path);            
        }
        
        // remove node from path for rest of discovery
        path.pop();
    }
    dfs(root, 0, []);
    return ans;
};

Variation #2: Number of paths between any two nodes and must be going through root with sum K

Variation #3: Number of paths between any two nodes and must be going downwards (not necessary with root) with sum K

https://leetcode.com/problems/path-sum-iii/description/

1. Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
2. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent to child nodes).

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    if(!root) {
        return 0;
    }
    let ans = 0;
    const map = new Map();
    map.set(0, 1);
    
    const dfs = (node, prefixSum) => { 
        // if null node
        if(!node) {
            return;
        }
        // update prefix sum
        prefixSum += node.val;
        
        // get ans
        const target = prefixSum - sum; 
        if(map.has(target)) {
            ans += map.get(target);
        }
        
        // update map
        if(!map.has(prefixSum)) {
            map.set(prefixSum, 0);
        }
        map.set(prefixSum, map.get(prefixSum) + 1);
        
        // explore left
        dfs(node.left, prefixSum);
        dfs(node.right, prefixSum);
        
        // backtrack prefix sum
        map.set(prefixSum, map.get(prefixSum) - 1);
        if(prefixSum !== 0 && map.get(prefixSum) === 0) {
            map.delete(prefixSum);
        }
        
    }
    
    dfs(root, 0)
    return ans;
};

LCA

Please refer to my existing blog :-)

Lowest common ancestor in a tree

Diameter of a binary tree

https://leetcode.com/problems/diameter-of-binary-tree/description/

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    let ans = 0;
    const dfs = node => { // Return the length of the longest path 
        // Base case: null node
        if(!node) {
            return 0;
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
        // Update global ans with local ans (no need to add 1 here as longest path already account the path length form current node)
        ans = Math.max(ans, left + right);

        // Return length of longest path
        return 1 + Math.max(left, right);

    }

    dfs(root);
    return ans;
};

The kth node in a binary search tree

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

Approach 1: Perform inorder and track the kth node

Time complexity: O(n)

Approach 2: Use subtree size to navigate the tree

Time complexity: O(h)

Number of nodes between p and q node in a binary search tree

Approach 1: Perform inorder and track the p and q node position

Time complexity: O(n)

Approach 2: Use subtree size to navigate the tree

Time complexity: O(h)

Happy coding :-)