A tree is a data structure that can have values of any data type and is made up of nodes, connected by edges.
What sets a tree apart from other data structures, such as an array or linked list, is that multiple ways exist to explore it. Tree depth-first search is a method to reduce the use of nested loops in our tree-related problems.
Depth-first search in a tree is usually implemented recursively. However, it can also be implemented iteratively with the help of a stack.
There are three main methods to solving a problem with the depth-first search pattern — Preorder, Inorder, and Postorder.
Preorder traversal: The preorder traverses the tree in the following three steps: Visit the root node; Recursively perform preorder traversal on the left child; Recursively perform pre-order traversal on the right child.
114 Flatten Binary Tree to Linked List
543 Diameter of Binary Tree
297 Serialize and Deserialize Binary Tree
Serialize a given binary tree to a file and deserialize it back to a tree. Make sure that the original and the deserialized trees are identical.
- Serialize: Write the tree to a file.
- Deserialize: Read from a file and reconstruct the tree in memory.
Serialize the tree into a list of integers, and then, deserialize it back from the list to a tree. For simplicity’s sake, there’s no need to write the list to the files.
226 Invert Binary Tree
Iterative Implementation
One way to think about and implement DFS is to start from the code for BFS and make two changes:
- swap in a stack data structure (which is last-in first-out) for the queue ( which is first-in first-out)
- postpone checking whether a vertex has already been explored until after removing it from the data structure
Recursive Implementation
Depth-first search also has an elegant recursive implementation.
// all vertices unexplored before outer call
mark s as explored
for each edge(s, v) in s's adjacency list do
if v is unexplored then
DFS(G, v)In this implementation, all recursive calls to DFS have access to the same set of global variables which track the vertices that have been marked as explored ( with all vertices initially unexplored). The aggressive nature of DFS is perhaps more obvious in this implementation — the algorithm immediately recurses on the first unexplored neighbor that it finds, before considering the remaining neighbors. In effect, the explicit stack data structure in the iterative implementation of DFS is being simulated by the program stack of recursive calls in the recursive implementation.
Depth First Search (DFS) technique to traverse a tree
We will be using recursion (or we can also use a stack for the iterative approach) to keep track of all the previous nodes while traversing. This also means that the space complexity will be O(H), where H is the maximum height of the tree.
Path Sum
Given a binary tree and a number S, find if the tree has a path from roof-to-leaf such that the sum of all the node values of that path equals S.
To recursively traverse a binary tree in a DFS fashion, we can start from the root and at every step, make two recursive calls one for the left and one for the right child.
- 1 Start DFS with the root of the tree
- 2 If the current node is not a leaf node, do two things:
* Subtract the value of the current node from the given number to get a new sum => S = S -node.value
* Make two recursive calls for both the children of the current node with the new number calculated in the previous step - 3 At every step, see if the current node being visited is a leaf and if its value is equal to the given number S. If both these conditions are true, we have found the required root-to-leaf path, therefore return true
- 4 If the current node is a leaf but its value is not equal to the given number S, return false
function hasPath(root, sum) {
if (!root) return false;
if (root.left === null && root.right === null) {
return root.val === sum;
} return hasPath(root.left, sum - root.val) ||
hasPath(root.right, sum - root.val);
Time complexity
The time complexity of the above algorithm is O(N), where N is the total number of nodes in the tree. This is due to the fact that we traverse each node once.
Space complexity
The space complexity of the above algorithm will be O(N) in the worst case. This space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e., every node has only one child).
Path Sum II
Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’.
There will be two differences from the above Path Sum problem:
- 1 Every time we find a root-to-leaf path, we will store it in a list
- 2 We will traverse all paths
function pathSum(root, sum) {
let allPaths = [];
let curPath = []; pathSumRecursive(root, sum, curPath, allPaths);
return allPaths;
}function pathSumRecursive(curNode, sum, curPath, allPaths) {
if (!curNode) return;
curPath.push(curNode.val);if (curNode.val === sum && !curNode.left && !curNode.right) {
allPaths.push([...curPath]);
} else {
pathSumRecursive(curNode.left, sum - curNode.val, curPath, allPaths);
pathSumRecursive(curNode.right, sum - curNode.val, curPath, allPaths);
} curPath.pop();
}
Time complexity
The time complexity of the above algorithm is O(N²), where N is the total number of nodes in the tree. This is due to the fact that we traverse each node once (which will take O(N)), and for every leaf node, we might have to store its path (by making a copy of the current path) which will take O(N).
We can calculate a tighter time complexity of O(NlogN) from the space complexity discussion below.
Space complexity
If we ignore the space required for the allPaths list, the space complexity of the above algorithm will be O(N) in the worst case. This space will be used to store the recursion stack. The worst-case will happen when the given tree is a linked list (i.e., every node has only one child).
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.
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 nodes to child nodes).
We can follow the same above DFS approach. But there will be four differences:
- 1 We will keep track of the current path in a list which will be passed to every recursive call
- 2 Whenever we traverse a node we will do two things:
* Add the current node to the current path
* As we added a new node to the current path, we should find the sums of all subpaths ending at the current node. If the sum of any subPath is equal to S, we will increment our path count - 3 We will traverse all paths and will not stop processing after finding the first path
- 4 Remove the current node from the current path before returning from the function. This is needed to Backtrack while we are going up the recursive call stack to process other paths.
