Binary Trees and Depth-First Search

Fundamentals

Depth-First Search (DFS) is an algorithm that is used to visit all nodes in a tree or graph-like data structure. We'll start by learning the order in which visits the nodes in a binary tree.

Binary Tree Properties

The top node of a binary tree is called the root. Each node in a binary tree can have at most two children, referred to as the left child and right child. A node that does not have any children is called a leaf node:

Height of a Binary Tree The height of a binary tree is the number of edges on the longest path between the root node and a leaf node. This is also known as the depth of the tree.

Balanced Binary Tree A binary tree is balanced if the height of the left and right subtrees of every node differ by at most 1.

A balanced binary tree.

An unbalanced binary tree.

Complete Binary Tree A binary tree is complete if every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Complete binary trees are an important concept in heap data structures.

A complete binary tree.

A complete binary tree has a height of O(log(n)), where n is the number of nodes in the tree.

Binary Search Tree A binary search tree (BST) is a binary tree where:

All nodes in the left subtree of the root have a value less than the root.
All nodes in the right subtree of the root have a value greater than the root.

The same property applies to all subtrees in the tree. This property allows for efficient search, insertion, and deletion of nodes in the tree.

A binary search tree. All nodes in the left subtree are less than 4, while all nodes in the right subtree are greater than 4.

Depth-First Search (DFS)

Depth-First Search is an algorithm used to traverse each node in a binary tree. It starts at the root node and tries to go "down" as far as possible until reaching a leaf node. When it reaches a leaf node, it "backtracks" to the parent node to explore the next path, which is animated below:

dfs

0 / 9

This "go deep as far as possible and then backtrack" behavior differentiates DFS from Breadth-First Search (BFS), which explores all the nodes at "level" before moving on to the next level.

Let's now look at the implementation of DFS on a binary tree. We'll pay special attention to the role that recursion and the call stack play in the algorithm.

Recursion and the Call Stack

Depth-First Search is typically implemented as a recursive function, or a function that calls itself within the body of the function.

def dfs(node):
    # base case
    if not node:
        return

    dfs(node.left) # recursive call
    dfs(node.right) # recursive call

Working with any recursive function requires a good understanding of the call stack. The call stack is a stack-like data structure that keeps track of the function calls that are currently being executed.

Below, we'll visualize how the call stack grows and shrinks as we traverse a binary tree using DFS. In particular, we'll learn how the call stack allows DFS to backtrack.

Call Frame

The initial call to dfs is made on the root node of the binary tree. This creates a call frame (the left panel below), which contains the current line of code being executed and the variables that are local to the function call.


def dfs(node):
  if node is None:
    return
  dfs(node.left)
  dfs(node.right)

node: Node(4)

dfs

The current line of execution is highlighted in blue. The local variables are node: Node(4).

Pushing to the Call Stack

Since node is not None, the first step of our dfs function is to visit the left child of the root node by making a recursive call to dfs(node.left).

This pushes a new call frame onto the call stack, where node: Node(2). Execution begins at the first line of code in this new call frame.


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(4)

dfs

0 / 1

Pushing a new call frame onto the call stack.

Base Case

As we make recursive calls to traverse down the tree, we keep pushing call frames onto the call stack until we reach our first base case, where node is None.

A base case is a condition that stops DFS from traversing down.


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(4)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(2)

0 / 2

Traversing down until reaching a base case.

Backtracking

Here, we reach our first return statement. When the function returns, the call frame is popped off the call stack, and execution returns to the call frame that is now at the top of the call stack. This is backtracking!

After backtracking, we make a recursive call to dfs(node.right), which is another base case that returns immediately.


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(4)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(2)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(1)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: None

0 / 3

Backtracking to the parent node.

Backtracking (continued)

At this point, we have finished visiting all the nodes in the left and right subtrees of the current node Node(1). The current call frame is popped off the call stack, and we backtrack to the parent node Node(2), which then makes a recursive call to dfs(node.right).

This process continues until we have visited all the nodes in the binary tree.


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(4)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(2)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(1)

0 / 15

Traversing the entire binary tree.

Time and Space Complexity

If there a N nodes in a binary tree, then a depth-first search based solution will visit each node exactly once.

Time Complexity: Find the work done per recursive call, and multiply it by N. All of the examples (aside from the merging lists example) perform a constant amount of work per recursive call, so the time complexity is O(N).

Space Complexity: The memory that each recursive call occupies on the call stack is part of the space complexity of a problem. In depth-first search problems, a recursive call is made for each node in the tree, so the space complexity is at least O(N). This is in addition to the amout of space required for each recursive call itself, which differs from problem to problem.

Summary

Depth-First Search visits every node in a binary tree by going "down" as far as possible before backtracking to visit the nodes on the next path.
Depth-First Search is typically implemented as a recursive function. It visits new nodes in the tree by making recurisve calls. When a recursive call is made, a new call frame is pushed onto the call stack.
Backtracking occurs whenever a recursive call returns. The call frame is popped off the call stack, and execution returns to the next call frame on the call stack.

Another key insight is that whenever a recursive function returns, we have finished visiting all nodes in the left and right subtrees of the current node. This leads us to Return Values, which is the first unit in solving binary tree problems with DFS.

Next: Return Values

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Introduction

Return Values

Fundamentals

Depth-First Search (DFS) is an algorithm that is used to visit all nodes in a tree or graph-like data structure. We'll start by learning the order in which visits the nodes in a binary tree.

Binary Tree Properties

Height of a Binary Tree The height of a binary tree is the number of edges on the longest path between the root node and a leaf node. This is also known as the depth of the tree.

Balanced Binary Tree A binary tree is balanced if the height of the left and right subtrees of every node differ by at most 1.

A balanced binary tree.

An unbalanced binary tree.

A complete binary tree.

A complete binary tree has a height of O(log(n)), where n is the number of nodes in the tree.

Binary Search Tree A binary search tree (BST) is a binary tree where:

All nodes in the left subtree of the root have a value less than the root.
All nodes in the right subtree of the root have a value greater than the root.

The same property applies to all subtrees in the tree. This property allows for efficient search, insertion, and deletion of nodes in the tree.

A binary search tree. All nodes in the left subtree are less than 4, while all nodes in the right subtree are greater than 4.

Depth-First Search (DFS)

dfs

0 / 9

This "go deep as far as possible and then backtrack" behavior differentiates DFS from Breadth-First Search (BFS), which explores all the nodes at "level" before moving on to the next level.

Let's now look at the implementation of DFS on a binary tree. We'll pay special attention to the role that recursion and the call stack play in the algorithm.

Recursion and the Call Stack

Depth-First Search is typically implemented as a recursive function, or a function that calls itself within the body of the function.

def dfs(node):
    # base case
    if not node:
        return

    dfs(node.left) # recursive call
    dfs(node.right) # recursive call

Below, we'll visualize how the call stack grows and shrinks as we traverse a binary tree using DFS. In particular, we'll learn how the call stack allows DFS to backtrack.

Call Frame


def dfs(node):
  if node is None:
    return
  dfs(node.left)
  dfs(node.right)

node: Node(4)

dfs

The current line of execution is highlighted in blue. The local variables are node: Node(4).

Pushing to the Call Stack

Since node is not None, the first step of our dfs function is to visit the left child of the root node by making a recursive call to dfs(node.left).

This pushes a new call frame onto the call stack, where node: Node(2). Execution begins at the first line of code in this new call frame.


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(4)

dfs

0 / 1

Pushing a new call frame onto the call stack.

Base Case

As we make recursive calls to traverse down the tree, we keep pushing call frames onto the call stack until we reach our first base case, where node is None.

A base case is a condition that stops DFS from traversing down.


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(4)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(2)

0 / 2

Traversing down until reaching a base case.

Backtracking

After backtracking, we make a recursive call to dfs(node.right), which is another base case that returns immediately.


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(4)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(2)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(1)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: None

0 / 3

Backtracking to the parent node.

Backtracking (continued)

This process continues until we have visited all the nodes in the binary tree.


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(4)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(2)


def dfs(node):
  if node is None:
    return

  dfs(node.left)
  dfs(node.right)

node: Node(1)

0 / 15

Traversing the entire binary tree.

Time and Space Complexity

If there a N nodes in a binary tree, then a depth-first search based solution will visit each node exactly once.

Summary

Depth-First Search visits every node in a binary tree by going "down" as far as possible before backtracking to visit the nodes on the next path.
Depth-First Search is typically implemented as a recursive function. It visits new nodes in the tree by making recurisve calls. When a recursive call is made, a new call frame is pushed onto the call stack.
Backtracking occurs whenever a recursive call returns. The call frame is popped off the call stack, and execution returns to the next call frame on the call stack.

Next: Return Values

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103