Coding Algorithms — Trees and Recursion

Trees are one of the most common type of interview questions asked in top tech companies. In probably >95% of the problems involving trees, it is solved by using recursion.

This is because trees inherently have a sub-problem structure.

Two of the common patterns are as follows:

• Compute some function F(root, inputs). Generally, we solve the sub-problems F(root.left, inputs) and F(root.right, inputs) and then use them to compute F(root, inputs) = G(F(root.left, inputs), F(root.right, inputs)) for some function G.
• Construct Tree under some constraints and given inputs (generally as arrays)

We look at some of the famous tree recursion problems asked during interviews.

Problem 1:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

Example:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Solution:

Let (a, b) = LCA(X, p, q)

where both a and b are boolean and ‘a’ is True if we have already found the LCA of p and q in the subtree rooted at node X else False and ‘b’ is True if we have found at-least one of p or q in the subtree rooted at node X else False.

Then if LCA(X.left, p, q) = (a1, b1) and LCA(X.right, p, q) = (a2, b2) and LCA(X, p, q) = (a, b), then we can say that:

a = a1 or a2 or (b1 and b2) or (b1 and (X==p or X==q)) or (b2 and (X==p or X==q))

b = b1 or b2 or X==p or X==q

In the above 2 equalities, special care must be taken to note that the current node X can be either p or q.

Time complexity is O(N) where N is the number of nodes in the Tree.

When we have to answer multiple queries with different p and q, then we can pre-process the tree using Binary Uplifting in O(N*logN) and then answer each query for the LCA in O(logN) time complexity. This is applicable only when the tree is static so that the ancestors computed with binary uplifting do not change.

LCA using Binary Uplifting.

Problem 2:

Given a N-ary Tree and 2 nodes P and Q, return True if Node P is an ancestor of Node Q.

Solution:

The solution to this problem comes from the above problem.

Let in_time[v] be the ‘time’ at which node ‘v’ is first encountered during DFS traversal and out_time[v] be the ‘time’ at which we exit ‘v’ i.e. out_time[v] ≥ max(in_time[u] for all children u of v).

Then for a node ‘w’ it is a descendant of node ‘v’ if in_time[w] > in_time[v] and out_time[w] ≤ out_time[v]

Time complexity is O(N) and space complexity is O(N) where N is the number of nodes in the Tree.

Problem 3:

There is a shopping mall where shops are arranged in a N-ary tree where the root is the entrance gate. From the gate (root) you visit all the nodes in the tree having a shop and eventually return back towards the root.

Find the total time to visit all the shops and return to the entrance of the mall. Time taken to traverse an edge is 1 time unit.

Solution:

Let the shops be denoted as ‘X’ on the tree. This is similar to the above problem where we need to visit the nodes in DFS manner and maintain out_time[v] for each node ‘v’.

But we do not visit any subtree not having any shops.

Final answer is the out_time[root].

If the out_time of a child node having at-least one shop is ‘t’, then we come back to the root node in time t+1 and go to the next child node at time t+2.

Time and space complexity is O(N).

Problem 4:

Given a dictionary of characters and their frequencies in text, construct a Huffman Encoding Tree of the characters.

{‘a’:1, ‘b’:2, ‘c’:3, ‘d’:3, ‘e’:3, ‘f’:4, ‘g’:4}

Each node is split in a way such that the smallest frequency character(s) goes to the left and the remaining goes to the right until there is only one character left.

If there are multiple characters with same frequency they are equally divided into left and right sub-trees.

Solution:

Idea is to use a min-heap data structure.

Create a min-heap where each node has the key as the frequency F and additionally also contains the list of characters with the corresponding frequency F.

At each node of the tree, remove the smallest frequency node from the heap.

If the remaining heap is empty, it implies that this is the only frequency present and if the current list of characters has only single element then we create a leaf node else we divide the list into 2 equal parts and create the left and right subtrees recursively.

If the remaining heap is non-empty, then we send the remaining heap to the right subtree of the node.

Time complexity is O(N*logN).

Problem 5:

Given a root of a tree. The tree may be of any depth and width, i.e. each node may have any number of child nodes.

This method should transform a tree in such a way that each node (except probably one) would either have N or 0 children (and one node may have a number of children between 0 and N).

Algorithm may transform given tree in any way with only condition:

• Node A was an ascendant of Node B in a source tree node
• B may not be an ascendant of a node A in a result tree (they may become siblings though).

Solution:

Store the nodes along with levels in a min-heap, do BFS traversal and for each node, extract maximum N nodes from the heap and add them as children of the current node and also add these nodes into the queue for further BFS traversal.

This guarantees that no descendant node in the original tree becomes ancestor node in the modified tree.

Time complexity is O(N*logN) and space complexity is O(N).

Problem 6:

Treap

A binary tree has the binary search tree property (BST property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys in its right subtree are larger than its own key.

It has the heap property if, for every node, the keys of its children are all smaller than its own key.

You are given a set of binary tree nodes (i, j) where each node contains an integer i and an integer j. No two i values are equal and no two j values are equal. We must assemble the nodes into a single binary tree where the i values obey the BST property and the j values obey the heap property.

Example 1:

Input: [(1, 6), (3, 7), (2, 4)]
Output:
		(3, 7)
		/
	 (1, 6)
		\
	  (2, 4)

Example 2:

Input: [(1, 4), (8, 5), (3, 6), (10, -1), (4, 7)]
Output:
		(4, 7)
		/    \
	(3, 6)   (8, 5)
	 /          \
 (1, 4)       (10, -1)

Solution:

Insert the tuples in a max-heap with key as the 2nd element of the tuple. Then one by one extract the root of the heap and insert the node based on BST property by starting from the root node, i.e. if the 1st element of the tuple is less than the 1st element of root, then go left else go right recursively.

Time complexity is O(N*logN) and space complexity is O(N).

Problem 7:

Tree command line utility — Given a tree data structure, print the tree similar to the ‘tree’ command line utility.

Solution:

This can be done recursively using DFS and iteratively using stack as follows:

For a program that prints the files in a directory using ‘tree’ command:

Problem 8:

Cartesian Tree — Given an integer array A, construct a tree that satisfies the following properties:

• Binary Tree
• Min Heap
• In order traversal returns original tree.

Solution:

One simple solution that uses extra space is by using min-heap to store the array and a hash-map to store the index of each element since every element is unique.

Whenever we extract an element from the root of min-heap, based on the original index we decide whether to go left or right of the current root. If the original index is greater than original index of root, go right else go left.

This way we guarantee that in-order property is preserved.

Time complexity is O(N*logN)

Another solution that do not use any additional data structures is as follows:

1. Take the current element from array
2. If the cartesian tree is empty, make this the root of the tree
3. Else if root is greater than the element, make the root as the left child of the new node and make this as the new root
4. Else if root is smaller than the element, recursively go down the right subtree, until we find an element greater than the current element. Replace the greater node with the current element and make the greater node as the left child.

Time complexity is O(N*logN).

Problem 9:

Design a tree-based data structure to efficiently manipulate a very long string.

class LongString {
	public LongString(String s) {
		// todo
	}
	
	/**
	* Returns the character at position 'i'.
	*/
	public char charAt(int i) {
		// todo
	}
	/**
	* Deletes the specified character substring.
	* The substring begins at the specified 'start' and extends to the character at index 'end - 1' or to the end of the sequence
	* if no such character exists.
	* If 'start' is equal to 'end', no changes are made.
	*
	* @param      start  The beginning index, inclusive.
	* @param      end    The ending index, exclusive.
	* @throws     StringIndexOutOfBoundsException  if 'start' is negative, greater than length, or greater than 'end'.
	*/
	public void delete(int start, int end) {
		// todo
	}
}

Solution:

Naive solution for ‘char_at’ query would be returned in O(1) using the string index but for delete we have to shift all the characters and worst case is O(N).

We can store the tree in a data structure similar to Segment Tree. The leaves of the tree will store the characters and each internal node of the tree will store how many characters are present in the subtree.

Time complexity for char_at query is O(logN) and for delete it is O(K*logN).

In fact, such a data structure can also be used to efficiently concatenate two strings.

Normally we would copy one string to another and then copy the next string at the end which is O(N+M) but with such a data structure as above, it can be achieved in O(1) by creating a new node as the root and count as sum of the counts of the root nodes of the individual strings.

Thus this data structure is better suited for use cases where we have frequent deletions of small ranges and/or concatenations but less frequent ‘char_at’ queries. Applications such as online text documents.

Problem 10:

Given the root of a complete binary tree, return the number of the nodes in the tree.

Every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Solution:

Straightforward solution is to count the number of nodes using BFS or DFS which is O(n).

But we can use the fact that this is a complete binary tree.

Let depth_right(node) denote the number of nodes we need to traverse starting from ‘node’ and follow only the right subtree only each time.

If depth_right(node) = depth_right(node.left), it implies that the “missing” node is in the right subtree else if depth_right(node) > depth_right(node.left) then it implies that the “missing” node is in the left subtree.

If the “missing” node is in the right subtree, then the left subtree is full tree i.e. number of nodes = 2^h where h is the height of left subtree, else if missing node is in the left subtree, then the right subtree is also a full subtree but with height-1 i.e. number of nodes = 2^(h-1).

Depending on which side is the “missing” node, we recursively traverse that direction only in each step.

Time complexity is O(logN).

Problem 11:

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Solution:

The possibilities are:

1. Thief robs the root — Then skips the left and right subtree root nodes and continues from the children of the left and right subtree root nodes.
2. Thief does not rob the root — Continues robbing the left and right subtree. May or may not rob the left and right subtree roots.

Time complexity is O(N) and space complexity is O(N) for the caching variable ‘dp’.

Problem 13:

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Solution:

The possibilities are:

1. The path includes the current root.
2. The path do not current root.

Let F(node) be the maximum path sum rooted at node but calculated along either left or right subtrees, whereas G(node) be the maximum path sum rooted at node calculated along both left and right subtrees.

F(node) = max(F(node.left)+node.val, F(node.right)+node.val, node.val)

G(node) = max(F(node.left)+F(node.right)+node.val, G(node.left), G(node.right), F(node))

Each recursion call returns 2 values, the first one is G(node) and 2nd one is F(node).

Time complexity is O(N).

Problem 14:

Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example:

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Solution:

At each node in the tree, we calculate these 4 values:

1. Sum of the subtree rooted at node.
2. Is it a BST — Boolean
3. Minimum value of any node of the subtree rooted at node.
4. Maximum value of any node of the subtree rooted at node.

These values can be calculated recursively.

Time complexity is O(N).

Problem 15:

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Example:

Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Solution:

For a given root node, let F(node) be the minimum number of cameras required to monitor all nodes in its subtree (but not necessarily itself).

The possible situations are:

1. Camera is installed at root node
2. Camera is not installed at root node

For the 2nd case, we can have different situations such as:

2a. Camera is installed at root of left subtree but not at root of right subtree.

2b. Camera is installed at root of right subtree but not at root of left subtree.

2c. Camera is installed at root of left subtree and also at root of right subtree.

2d. Camera is not installed at root of left subtree and also not at root of right subtree.

For the cases 1, 2(a), 2(b) and 2(c), the root node is also monitored.

We can thus reduce the possibilities to 3:

a. Camera is installed at root node and root is monitored.

b. Camera is not installed at root node but root is monitored by having at-least one subtree root having a camera installed.

c. Camera is not installed at root node and also root is not monitored.

Thus F(node) = min(a, b, c)

Let G(node) be the minimum number of cameras required to monitor all nodes in its subtree and also itself.

Thus G(node) = min(a, b)

a, b and c can be computed recursively:

Time complexity is O(N)

Problem 16:

You are given the root of a binary tree with n nodes where each nodein the tree has node.val coins. There are n coins in total throughout the whole tree.

In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.

Return the minimum number of moves required to make every node have exactly one coin.

Example:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Solution:

Let dp[root] be the tuple [a, x] where a is the total coins in the subtree rooted at root and x is the total number of nodes in the subtree rooted at root.

From the root we send x_left-a_left number of coins to the left subtree if x_left > a_left, else if x_left < a_left, then we send -(x_left-a_left) number of coins from left subtree to root.

Similarly, we send x_right-a_right number of coins to the right subtree if x_right > a_right, else if x_right < a_right, then we send -(x_right-a_right) number of coins from right subtree to root.

Then we can recursively distribute the coins.

Time and space complexity is O(N).