DSA Tree DFS Patterns
A tree DFS pattern is one recursive walk that returns a small answer from each subtree. Changing the returned value turns the same walk into a height, a count, or a yes-or-no answer.
Height returns a number
The height walk returns the longest downward path in edges. An empty child returns minus one, so a leaf returns zero.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def height(node, visits):
if node is None:
return -1
visits[0] += 1
left = height(node.left, visits)
right = height(node.right, visits)
return 1 + max(left, right)
tree = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(8))
visits = [0]
print("Height:", height(tree, visits))
print("Visits:", visits[0])Count returns a number
The count walk returns how many nodes sit in the subtree. Each node adds one for itself to its two child counts.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def count(node, visits):
if node is None:
return 0
visits[0] += 1
return 1 + count(node.left, visits) + count(node.right, visits)
tree = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(8))
visits = [0]
print("Count:", count(tree, visits))
print("Visits:", visits[0])Search returns True or False
The search walk returns whether the target sits in the subtree. Finding the target stops that branch of the walk early.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def contains(node, target, visits):
if node is None:
return False
visits[0] += 1
if node.value == target:
return True
return contains(node.left, target, visits) or contains(node.right, target, visits)
tree = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(8))
visits = [0]
print("Contains 4:", contains(tree, 4, visits))
print("Visits for 4:", visits[0])
visits = [0]
print("Contains 6:", contains(tree, 6, visits))
print("Visits for 6:", visits[0])Example
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def height(node, visits):
if node is None:
return -1
visits[0] += 1
return 1 + max(height(node.left, visits), height(node.right, visits))
def count(node, visits):
if node is None:
return 0
visits[0] += 1
return 1 + count(node.left, visits) + count(node.right, visits)
def contains(node, target, visits):
if node is None:
return False
visits[0] += 1
if node.value == target:
return True
return contains(node.left, target, visits) or contains(node.right, target, visits)
tree = TreeNode(5,
TreeNode(3, TreeNode(1), TreeNode(4)),
TreeNode(8, TreeNode(7), TreeNode(9)))
visits = [0]
print("Height in edges:", height(tree, visits))
print("Height visits:", visits[0])
visits = [0]
print("Node count:", count(tree, visits))
print("Count visits:", visits[0])
visits = [0]
print("Contains 9:", contains(tree, 9, visits))
print("Search visits for 9:", visits[0])
visits = [0]
print("Contains 6:", contains(tree, 6, visits))
print("Search visits for 6:", visits[0])Key points
- Subtree answer: the answer for one node together with everything below it
- A DFS pattern visits a node, then combines the answers from its two children
- Height returns a number in edges, and a leaf returns zero
- Count returns a number, and each node adds one for itself
- Search returns True or False, and one True child makes the parent True
In this example, one tree of seven nodes is measured three ways. The height walk finds a longest path of two edges and visits all seven nodes. The count walk also visits all seven nodes and returns seven. The search walk finds 9 on its seventh visit and never finds 6, so it also visits all seven nodes.
Note
One walk visits every node once, so three walks over seven nodes make 21 visits in total
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A DFS walk returns 1 plus the larger child answer, and an empty child returns -1. What does it return for a single node?