DFS on binary tree

Question

Implement a depth-first search (DFS) algorithm to traverse a binary tree. Given the root node of a binary tree, return the values of the nodes in the order they are visited during the DFS traversal. The output should be a list of node values.

Codemia · Accepted Answer

The problem requires us to perform a depth-first search (DFS) on a binary tree, which is a common graph traversal technique. In this case, DFS can be implemented using recursion or an explicit stack. The goal is to visit each node in the binary tree and collect their values in the order they are visited. The DFS pattern is suitable here because it allows us to explore as far down a branch as possible before backtracking, which aligns well with the hierarchical structure of a binary tree.

We will use a recursive DFS approach. The steps are as follows:

1. **Base Case**: If the current node is NULL, we return immediately since there is nothing to process.
2. **Process the Current Node**: Add the value of the current node to our result list.
3. **Recur on Left Subtree**: Call the DFS function on the left child of the current node.
4. **Recur on Right Subtree**: Call the DFS function on the right child of the current node.

For example, given the binary tree:
```
      1
     / \
    2   3
   / \
  4   5
```
The DFS traversal would visit nodes in the order: 1, 2, 4, 5, 3.

Here is the Python implementation of the DFS algorithm for the binary tree:

```python
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def dfs_traversal(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.value)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return result
```
This code defines a `TreeNode` class and a `dfs_traversal` function that performs the DFS.

The time complexity of the DFS traversal is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once. The space complexity is O(h), where h is the height of the tree. This space is used by the call stack during recursion. In the worst case (unbalanced tree), h can be n, leading to O(n) space complexity, while in a balanced tree, h is log(n), leading to O(log(n)) space complexity.

1. **Empty Tree**: If the root node is None, the function should return an empty list.
   - Input: `None`
   - Output: `[]`

2. **Single Node Tree**: A tree with only one node should return a list containing that single node's value.
   - Input: `TreeNode(1)`
   - Output: `[1]`

3. **Unbalanced Tree**: Ensure that the function handles cases where all nodes are either left or right children, which could affect the depth but not the correctness of the traversal.

DFS on binary tree

Figma

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Figma Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string