Binary tree pattern

A binary tree is a hierarchical data structure where each node has at most two children: a left child and a right child.

An n-ary tree is a data structure where each node can have up to n children, instead of just two like a binary tree. This makes them more flexible for representing data structures with varying degrees of branching.

A general tree is a hierarchical data structure where each node can have an arbitrary number of children, from zero to infinity. This flexibility makes them suitable for representing complex structures that don’t have a fixed branching pattern.

A rooted tree is a hierarchical data structure where a specific node is designated as the “root,” and all other nodes are connected to it through a series of edges. This creates a parent-child relationship between nodes, making it a more structured representation compared to non-rooted trees.

A non-rooted tree is a graph where every pair of distinct vertices is connected by a unique path. Unlike rooted trees, there is no designated “root” node, and the nodes are not organized in a hierarchical manner.

How can we run general tree algorithm on n-ary tree?

We have discussed many general tree algorithm in the following post.

Patterns to solve General Tree problems

Many times n-ary tree complex questions are based on the general tree/graph based pattern.

So the question is, can we easily modify n-ary into general tree and solve the problem?

Answer is yes. We will need to do one pass tree traversal to establish the parent relationship. After that for each node the list of neigbors will be [parent, child1, child2.....childn] .

Once we have modified getNeighbors() then we can easily run all types of general tree/graph algorithm on n-ary tree.

Please also note; there are many standard n-ary tree algorithm which are much better compare to the general tree, therefore we will first try to use the n-ary specific algorithm before jump on applying general tree.

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/

Hashmap-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 map 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 .

Construct 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.

Approach: Use inorder traversal

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;
}

426. Convert Binary Search Tree to Sorted Doubly Linked List

https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/description/

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Example 1:

Input: root = [4,2,5,1,3]

Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Approach# Apply inorder traversal

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;
};

314. Binary Tree Vertical Order Traversal

https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Approach

We can assign a two dimensional index <row, col> to each node as below.

Row wise order (regular bfs)

Each node can be assigned to a specific row, based on its level (i.e. the vertical distance to the root node).

Let us assume that the root node has a row index of 0, then both its child nodes would have the row index of 1.

This can be easily calculated running regular bfs .

Column wise order (Use hashmap to group nodes on same index)

Based on the relative offset to the root node of the tree, each node can be aligned to specific column .

Let us assume that the root node has a column index of 0, then its left child node would have a column index of -1 and its right child node would have a column index of +1, and so on.

Goals here is to order nodes by column first, then sort it based on row .

Following is the code to implement this approach.

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalOrder = function (root) {
    if (!root) {
        return [];
    }
    const map = new Map();
    const queue = [[root, 0]];
    while (queue.length > 0) {
        const [node, col] = queue.shift();
        if (!map.has(col)) {
            map.set(col, []);
        }
        map.get(col).push(node.val)
        if (node.left) {
            queue.push([node.left, col - 1]);
        }
        if (node.right) {
            queue.push([node.right, col + 1]);
        }
    }
    const keys = Array.from(map.keys());
    keys.sort((a, b) => a - b);
    return keys.map(key => map.get(key));
};

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/

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Approach

1. Use running sum and running path discover so far for each node.
2. Once returning from the recursion function call, backtrack node from path i.e. remove. Since path is a reference variable therefore backtrack is required. No change is required intotal as it is primitive value.

Following is code for reference.

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).

Approach

We can use prefix sum optimized approach to count the window sum. Following is code for reference.

/**
 * @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
        map.set(prefixSum, map.has(prefixSum)? map.get(prefixSum)+1: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/

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Approach

1. For every node, we can check the longest path in left and right subtree.
2. This gives longest path between any two nodes as left+right . We can update the global ans with this.
3. We can use dfs() post order processing to implement this.

/**
 * @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 from current node
        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)

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
    let ans = -1;
    let counter = 0;
    const dfs = node => {
        if (!node) {
            return;
        }
        dfs(node.left);
        // In-order zone
        counter++;
        if (counter === k) {
            ans = node.val;
        }
        dfs(node.right);
    }
    dfs(root);
    return ans;
};

Approach 2: Use rank of node

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

If we ignore the nature of binary search tree then can simply run the in-order dfs to traverse each node and count it.

const getCount = (root, p, q) => {
  let ans = 0;
  const dfs = node => {
    if(!node) {
       return;
    }    
    dfs(node.left);
    // Use in-order location for ans
    if(node.val >= p.val && node.val <= q.val) {
      ans++;
    }
    dfs(node.right);
  }
  dfs(root);
  return ans;
}

Time complexity: O(n)

Approach 2: Use subtree size to navigate the tree

We can leverage the nature of binary search tree as below.

1. If current node is in the range of [low, high] then we can count it and explore both left subtree and right subtree.
2. If current node is less than low node then no need to explore left subtree as these will be smaller than the low therefore will not be part of the answer.
3. Similarly if current node is higher than high then no need to explore the right subtree. We can only explore the left subtree.

const getCount = (root, p, q) => {
  const dfs = node => {
    if(!node) {
       return 0;
    }
    // If in the range then recurse both
    if(node.val >= p.val && node.val <= q.val) {
      return 1 + dfs(node.left) + dfs(node.right);
    }
    // If lower than low then no need to explore left subtree
    if(node.val < p.val) {
       return dfs(node.right)
    }
    // Here node is higher than high therefore no need to explore the right subtree
    return dfs(node.left);
  }
  return dfs(root);
}

Time complexity: O(h)

938. Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

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

/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function (root, low, high) {
    let ans = 0;
    const dfs = (node) => {
        if (!node) {
            return;
        }
        // process each node
        const val = node.val;
        if (val >= low && val <= high) {
            ans += val;
        }
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return ans;
};

Approach 2: Use subtree size to navigate the tree

/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function (root, low, high) {
    const dfs = (node) => {
        if (!node) {
            return 0;
        }
        // if node is in range [low, high] then explore both left and right
        const val = node.val;
        if (val >= low && val <= high) {
            return val + dfs(node.left) + dfs(node.right);
        }
        // If current node is lower than low then skip left subtree
        if (val < low) {
            return dfs(node.right);
        }
        // If current node is higher than high then skip right subtree
        return dfs(node.left);
    }
    return dfs(root);
};

965. Univalued Binary Tree

A binary tree is uni-valued if every node in the tree has the same value.

Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.

Approach

A tree is univalued if both its children are univalued, plus the root node has the same value as the child nodes.

const dfs = node => {
    let isLeftUnival = true;
    if(node.left) {
        isLeftUnival = (node.val === node.left.val) && dfs(node.left);
    }
    let isRightUnival = true;
    if(node.right) {
        isRightUnival = (node.val === node.right.val) && dfs(node.right);

    }
    return isLeftUnival && isRightUnival;
}
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isUnivalTree = function(root) {
    if(!root) {
        return true;
    }
    return dfs(root);
};

863. All Nodes Distance K in Binary Tree

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

Approach 1 # Establish parent pointer then run a general graph algorithm

In pass #1, we can establish parent relationship for each node, it convert given binary tree into a general undirected graph where node’s neighbor can be find out by [left, right, parent] .

Then we can simply run the dfs or bfs and find out all the nodes at the distance k .

Time complexity: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
const addParent = (node, parent) => {
    if (!node) {
        return;
    }
    node.parent = parent;
    addParent(node.left, node);
    addParent(node.right, node);
}
const searchNodesAtDistanceK = (node, d, ans, visited) => {
    if (!node) {
        return;
    }
    if (visited.has(node)) {
        return;
    }
    visited.set(node, true);
    if (d === 0) {
        ans.push(node.val);
        return;
    }
    const neighbors = [node.left, node.right, node.parent];
    for (const neighbor of neighbors) {
        searchNodesAtDistanceK(neighbor, d - 1, ans, visited);
    }
}
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function (root, target, k) {
    addParent(root, null);
    const ans = [];
    const visited = new Map();
    searchNodesAtDistanceK(target, k, ans, visited);
    return ans;
};

Approach 2# Convert tree into graph and then run k distance node algorithm

We can first convert tree into undirected graph then we can run the k distance node algorithm.

Time complexity: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
const buildGraph = (node, parent, graph) => {
    if (!node) {
        return;
    }
    if (!graph.has(node)) {
        graph.set(node, []);
    }
    const neighbors = [parent, node.left, node.right];
    for (const neighbor of neighbors) {
        if (neighbor) {
            graph.get(node).push(neighbor);
        }
    }
    buildGraph(node.left, node, graph);
    buildGraph(node.right, node, graph);
}
const searchNodesAtDistanceK = (graph, node, d, ans, visited) => {
    if (visited.has(node)) {
        return;
    }
    visited.set(node, true);
    if (d === 0) {
        ans.push(node.val);
        return;
    }
    for (const neighbor of graph.get(node)) {
        searchNodesAtDistanceK(graph, neighbor, d - 1, ans, visited);
    }
}
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function (root, target, k) {
    const graph = new Map();
    buildGraph(root, null, graph);
    const ans = [];
    const visited = new Map();
    searchNodesAtDistanceK(graph, target, k, ans, visited);
    return ans;
};

Approach 3# Pass info from top to bottom and bottom to up and followed by searching on opposite side

We can take following approach.

1. We need to find distance from the target node. Let manager to keep passing distance=0 to child worker node until find the target node.
2. Once we find the target node then we will keep incrementing distance++ for each sub tree node. Once reach to node with distance==k then include node as answer. Return early for early pruning.
3. During recursion windup, let worker to return distance=0 if it is not target node or it doesn’t have target node in its subtree.
4. Otherwise if it is target node then worker will return distance=1to parent node.
5. When manager receives distance > 0 then it will increment distance++ and launch another recursion on the opposite side of subtree.

Time complexity = O(n) + O(n) ~ O(n)

Following is code to implement this approach.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function (root, target, k) {
    // Edge case
    if (k === 0) {
        return [target.val];
    }
    const ans = [];
    const recursion = (node, distance) => {
        if (!node) {
            return 0;
        }
        // If reached to node at distnace k then include it in ans
        if (distance === k) {
            ans.push(node.val);
            return 0; // prune early
        }
        // If found target node or subtree has target node then launch recursion 
        let left, right = 0;
        if (node.val === target.val || distance > 0) {
            left = recursion(node.left, distance + 1);
            right = recursion(node.right, distance + 1);
        } else {
            // Otherwise simply propagte 0
            left = recursion(node.left, 0);
            right = recursion(node.right, 0);
        }
        // If a node receives a k in return it is k-th distant parent from the the target.
        if (left === k || right === k) {
            ans.push(node.val);
            return 0;
        }
        // If target node then return 1
        if (node.val === target.val) {
            return 1;
        }
        // If either left or right is > 0 then it means need to search opposite subtree
        if (left > 0) {
            recursion(node.right, left + 1);
        }
        if (right > 0) {
            recursion(node.left, right + 1);
        }
        // if subtree has target then increment and return
        if (left > 0 || right > 0) {
            return left > 0 ? left + 1 : right + 1;
        }
        // Otherwise return 0
        return 0;
    }
    recursion(root, 0);
    return ans;
};

2385. Amount of Time for Binary Tree to Be Infected

https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/description/

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.

Each minute, a node becomes infected if:

• The node is currently uninfected.
• The node is adjacent to an infected node.

Return the number of minutes needed for the entire tree to be infected.

Approach #1: Add parent relationship and then run a general graph algorithm to find out the longest distance node

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function (root, start) {
    let target = null;
    const addParent = (node, parent) => {
        if (!node) {
            return;
        }
        if (node.val === start) {
            target = node;
        }
        node.parent = parent;
        addParent(node.left, node);
        addParent(node.right, node);
    }
    const visited = new Map();
    let ans = 0;
    const traversing = (node, distance) => {
        if (visited.has(node)) {
            return;
        }
        visited.set(node, true);
        ans = Math.max(ans, distance);
        const neighbors = [node.left, node.right, node.parent];
        for (const neighbor of neighbors) {
            if (neighbor) {
                traversing(neighbor, distance + 1);
            }
        }
    }
    addParent(root, null);
    traversing(target, 0);
    return ans;
};

Approach #2: Convert into graph then run a general graph algorithm to find out the longest distance node

Approach #3 One pass DFS

1. If the node with the value start happened to be the root, the maximum distance from the start node would be equivalent to the maximum depth of the tree.
2. Can we determine the max distance of the start node using the depths of sub-trees?

Here is the basic recursive algorithm for finding the maximum depth, which we will adjust to our needs.

1. If root = null return 0.
2. Make a recursive call with root.right and save as rightDepth.
3. Make a recursive call with root.left and save as leftDepth.
4. Return max(rightDepth, leftDepth) + 1.

One challenge to this task is identifying whether we have encountered the start node during the traversal. We can return a negative depth when we encounter the start node. This will flag that we have found the start node, and as we traverse the tree, whenever we encounter a negative depth, we know the subtree contains the start node.

There are four main cases:

1. If root is null, return 0.
2. root.val = start. If so, we return depth = -1 to signify this is the start node. In this way, in subsequent recursive calls, the parent node of the start node will know whether its child nodes contain the start node. Here we are also able to calculate the maxDistance of any node in the start node's subtree by finding the max of the left and right depth.
3. The left and right depth are both non-negative. If they are, we know the start node is not in this subtree, and we can set depth = max(leftDepth, rightDepth) just like with the basic max depth.
4. The final case is when the root is not the start node, but its subtree contains the start node. In this case, we will set depth = min(leftDepth, rightDepth) - 1, which will give us a negative number, the absolute value of which represents the distance of the start node to the root node. To calculate the distance from the start node to the furthest node in the other subtree, we will add the absolute value of the negative depth of the subtree that contains the start node, and the positive depth of the other subtree, for convenience, we can directly take the absolute value of two values. Then, we update maxDistance with distance if it is larger.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function(root, start) {
    let ans = 0;
    const traverse = node => {
        if(!node) {
            return 0;
        }
        let left = traverse(node.left, start);
        let right = traverse(node.right, start);
        let depth = 0;
        if(node.val === start) {
            ans = Math.max(left, right);
            depth = -1;
        } else if (left >=0 && right >=0) {
            depth = Math.max(left, right) + 1;
        } else {
            const distance = Math.abs(left) + Math.abs(right);
            ans = Math.max(ans, distance);
            depth = Math.min(left, right) - 1; 
        }
        return depth;
    }
    traverse(root);
    return ans;
};

450. Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/description

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]

Approach

Let’s revisit few related concepts relate to BST.

Successor: “after node”, i.e. the next node, or the smallest node after the current one. It’s also the next node in the inorder traversal. To find a successor, go to the right once and then as many times to the left as you could.

const successor = target => {
  let node = target.right;
  while (node && node.left) { 
    node = node.left;
  }
  return node;
} 

Predecessor : “before node”, i.e. the previous node, or the largest node before the current one. It’s also the previous node in the inorder traversal. To find a predecessor, go to the left once and then as many times to the right as you could.

const predecessor = target => {
  let node = target.left;
  while(noe && node.right) {
    node = node.right;
  }
  return node;
}

Approach: Use iterative version

1. Find the node with it’s parent.
2. If node is a leaf node then use the parent node to set null if exist as left vs right child. If parent is null then it means no more nodes in tree so return null.
3. If node has only left child: If parent is null then return the left node. Otherwise set node.left to the parent left vs right as per their relationship.
4. If node has only right child: If parent is null then return the right node. Otherwise set node.right to the parent left vs right as per their relationship.
5. If node has both left and right child: First find the successor of the node. Call same method recursively to delete the successor as deleteNode(node, successor.val) . Update the node value to successor.

Following is code for reference.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
const findNode = (root, key) => {
    let current = root;
    let parent = null;
    while (current) {
        // if match 
        if (current.val === key) {
            return [parent, current];
        }
        parent = current; // update parent
        if (current.val > key) {
            // move left
            current = current.left;
        } else {
            // move right
            current = current.right;
        }
    }
    return [parent, current];
}
const getMin = (root) => {
    let current = root;
    while (current && current.left) {
        current = current.left;
    }
    return current;
}
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
    const [parent, node] = findNode(root, key);
    if (!node) {
        return root;
    }

    // Use case 1: if leaf node
    if (!node.left && !node.right) {
        if (!parent) {
            return null;
        }
        if (parent.left === node) {
            parent.left = null;
        } else {
            parent.right = null;
        }
        return root;
    }
    // Use case 2.a: only has left child
    if (node.left && !node.right) {
        if (!parent) {
            return node.left;
        }
        if (parent.left === node) {
            parent.left = node.left;
        } else {
            parent.right = node.left;
        }
        return root;
    }

    // use case 2.b: only has right child
    if (!node.left && node.right) {
        if (!parent) {
            return node.right;
        }
        if (parent.left === node) {
            parent.left = node.right;
        } else {
            parent.right = node.right;
        }
        return root;
    }

    // use case 3: Has both left and right child
    const successor = getMin(node.right);

    // delete successor
    deleteNode(node, successor.val);

    // swap val
    node.val = successor.val;

    return root;
};

173. Binary Search Tree Iterator

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

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
• boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
• int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Approach

1. Keep track of root and current node in the class.
2. Initialize current= getMin() with the first node from in-order traversal.
3. To find the next() , we need to find out the next for the this.current .
4. We can find successor as below.
5. If current.right is not empty then simply run getMin(current) to get the successor
6. Otherwise, start searching for node starting from root
7. Keep track for anecestor variable and update when we take left trun.

Following is code for reference.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
const getMin = (root) => {
    // get left most node
    let node = root;
    while (node.left) {
        node = node.left;
    }
    return node;
}
const getSuccessor = (root, current) => {
    // if node has right child then get min in the right subtree
    if (current.right) {
        return getMin(current.right);
    }
    // get the ancestor who took first right turn
    let node = root;
    let ancestor = null;
    // keep searching for node
    while (node !== current) {
        if (current.val < node.val) {
            // track the node taking left turn
            ancestor = node;
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return ancestor;
}
/**
 * @param {TreeNode} root
 */
var BSTIterator = function (root) {
    this.root = root;
    this.current = getMin(root);
};
/**
 * @return {number}
 */
BSTIterator.prototype.next = function () {
    const ans = this.current;
    this.current = getSuccessor(this.root, this.current);
    return ans.val;
};
/**
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function () {
    return !!this.current;
};
/** 
 * Your BSTIterator object will be instantiated and called as such:
 * var obj = new BSTIterator(root)
 * var param_1 = obj.next()
 * var param_2 = obj.hasNext()
 */

99. Recover Binary Search Tree

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

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Example 1:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Approach#1: Convert to array, find mismatch then swap

class Solution {
private:
    vector<int> nums;
    unordered_map<int, TreeNode*> map;
    void dfs(TreeNode* node) {
        if(node == nullptr) {
            return;
        }
        dfs(node->left);
        int i = nums.size();
        map[i] = node;
        nums.push_back(node->val);
        dfs(node->right);
    }
    // 1,3,2,4 -> {2,1}
    pair<int,int> mismatch(vector<int> & nums) {
        int n = nums.size();
        int first = -1;
        int second = -1;
        for(int i=n-1; i > 0; i--) {
            if(nums[i] < nums[i-1]) {
                first=i;
                int j =0;
                while(j < i) {
                    if(nums[j] > nums[j+1]) {
                        second = j;
                        return make_pair(first, second);
                    }
                    j++;
                }
            }
        }
        return {};
    }
    
    void recover(TreeNode* root, pair<int,int> p) {
        auto[first, second] = p;
        TreeNode* firstNode = map[first];
        TreeNode* secondNode = map[second];
        // swap first and second node
        int temp = firstNode->val;
        firstNode-> val = secondNode->val;
        secondNode->val = temp;

    }
public:
    void recoverTree(TreeNode* root) {
        dfs(root);
        pair<int,int> p = mismatch(nums);
        recover(root, p);
    }
};

Approach#2: Run searching on tree

class Solution {
private:
    TreeNode* first = nullptr;
    TreeNode* second = nullptr;
    TreeNode* prev1 = nullptr;
    TreeNode* prev2 = nullptr;
    void findFirst(TreeNode* node) {
        if (node == nullptr || first != nullptr) {
            return;
        }
        findFirst(node->left);
        if (prev1 != nullptr) {
            if (prev1->val > node->val) {
                first = prev1;
                return;
            }
        }
        prev1 = node;
        findFirst(node->right);
    }
    void findSecond(TreeNode* node) {
        if (node == nullptr || second != nullptr) {
            return;
        }
        // scan from right to left
        findSecond(node->right);
        if (prev2 != nullptr) {
            if (prev2->val < node->val) {
                second = prev2;
                return;
            }
        }
        prev2 = node;
        findSecond(node->left);
    }
    void swap(TreeNode* first, TreeNode* second) {
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }

public:
    void recoverTree(TreeNode* root) {
        findFirst(root);
        findSecond(root);
        swap(first, second);
    }
};

545. Boundary of Binary Tree

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary.

The left boundary is the set of nodes defined by the following:

• The root node’s left child is in the left boundary. If the root does not have a left child, then the left boundary is empty.
• If a node in the left boundary and has a left child, then the left child is in the left boundary.
• If a node is in the left boundary, has no left child, but has a right child, then the right child is in the left boundary.
• The leftmost leaf is not in the left boundary.

The right boundary is similar to the left boundary, except it is the right side of the root’s right subtree. Again, the leaf is not part of the right boundary, and the right boundary is empty if the root does not have a right child.

The leaves are nodes that do not have any children. For this problem, the root is not a leaf.

Given the root of a binary tree, return the values of its boundary.

Example 1:

Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10]
Output: [1,2,4,7,8,9,10,6,3]
Explanation:
- The left boundary follows the path starting from the root's left child 2 -> 4.
  4 is a leaf, so the left boundary is [2].
- The right boundary follows the path starting from the root's right child 3 -> 6 -> 10.
  10 is a leaf, so the right boundary is [3,6], and in reverse order is [6,3].
- The leaves from left to right are [4,7,8,9,10].
Concatenating everything results in [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3].

Approach# 1: Apply given traversal rule

Divide this problem into three subproblems- left boundary, leaves and right boundary.

• Left Boundary: We keep on traversing the tree towards the left and keep on adding the nodes in the res array, provided the current node isn’t a leaf node. If at any point, we can’t find the left child of a node, but its right child exists, we put the right child in the res and continue the process.
• Leaf Nodes: We make use of a recursive function addLeaves(res,root), in which we change the root node for every recursive call. If the current root node happens to be a leaf node, it is added to the res array. Otherwise, we make the recursive call using the left child of the current node as the new root. After this, we make the recursive call using the right child of the current node as the new root.
• Right Boundary: We perform the same process as the left boundary. But, this time, we traverse towards the right. If the right child doesn’t exist, we move towards the left child. Also, instead of putting the traversed nodes in the res array, we push them over a stack during the traversal. After the complete traversal is done, we pop the element from over the stack and append them to the res array.

Following is code for reference.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
private:
    bool isLeaf(TreeNode* node) {
        if (node->left == nullptr && node->right == nullptr) {
            return true;
        }
        return false;
    }
    void addLeft(TreeNode* node, vector<int>& ans) {
        if (node == nullptr) {
            return;
        }
        if (!isLeaf(node)) {
            ans.push_back(node->val);
        }
        if (node->left != nullptr) {
            addLeft(node->left, ans);
        } else {
            addLeft(node->right, ans);
        }
    }
    void addLeaves(TreeNode* node, vector<int>& ans) {
        if (node == nullptr) {
            return;
        }
        if (isLeaf(node)) {
            ans.push_back(node->val);
        } else {
            if (node->left != nullptr) {
                addLeaves(node->left, ans);
            }

            if (node->right != nullptr) {
                addLeaves(node->right, ans);
            }
        }
    }
    void addRight(TreeNode* node, vector<int>& ans) {
        if (node == nullptr) {
            return;
        }
        if (!isLeaf(node)) {
            ans.push_back(node->val);
        }
        if (node->right != nullptr) {
            addRight(node->right, ans);
        } else {
            addRight(node->left, ans);
        }
    }

public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) {
            return ans;
        }
        if (!isLeaf(root)) {
            ans.push_back(root->val);
        }
        addLeft(root->left, ans);
        addLeaves(root, ans);
        vector<int> right;
        addRight(root->right, right);
        for (int i = right.size() - 1; i >= 0; i--) {
            ans.push_back(right[i]);
        }
        return ans;
    }
};

Happy coding :-)