Home/

...

/

Introduction

Introduction

Real-world problems

Depth-first search can be used to find the longest route for an Uber driver to maximize the possibility of finding customers.

A city cannot be represented by a single straight road because there are numerous intersections and crossings running through it. In our city, there are forks in the road, making binary-tree representation possible. The furthest checkpoints of the city are leaf nodes in this binary tree; these represent the Uber service area’s limits.

Since the city can be represented as a binary tree, the longest path will be the one with the maximum number of edges between two nodes or checkpoints. This is shown in purple in the following illustration:

Dry-run templates

This is the implementation of the solution provided for the problem posed in the All Paths for a Sum (medium) lesson:

Press + to interact
Python 3.5
class TreeNode:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
def find_paths(root, required_sum):
  allPaths = []
  find_paths_recursive(root, required_sum, [], allPaths)
  return allPaths
def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
  if currentNode is None:
    return
  # add the current node to the path
  currentPath.append(currentNode.val)
  # if the current node is a leaf and its value is equal to required_sum, save the current path
  if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
    allPaths.append(list(currentPath))
  else:
    # traverse the left sub-tree
    find_paths_recursive(currentNode.left, required_sum -
                         currentNode.val, currentPath, allPaths)
    # traverse the right sub-tree
    find_paths_recursive(currentNode.right, required_sum -
                         currentNode.val, currentPath, allPaths)
  # remove the current node from the path to backtrack,
  # we need to remove the current node while we are going up the recursive call stack.
  del currentPath[-1]
def main():
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.left.left = TreeNode(4)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  required_sum = 23
  print("Tree paths with required_sum " + str(required_sum) +
        ": " + str(find_paths(root, required_sum)))
main()

Sample input #1

root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(4)
root.right.left = TreeNode(10)
root.right.right = TreeNode(5)
required_sum: 23

    _ 12 _ 
   |      |
 _ 7   __ 1 _ 
|     |      |
4     10     5

We’ll start our path search from the root of our tree.

Line number

current root

Recursive call

currentNode

required_sum

currentPath

allPaths

45

12

-

-

23

-

-

14-19

12

-

12

23

[12]

[12]

26-27

12

Left subtree

7

11

[12, 7]

[ ]

26-27

7

Left subtree

4

4

[12, 7, 4]

[ ]

22-23

7

-

4

4

[12, 7, 4]

[[12, 7, 4]]

34

7

Backtracking

4

4

[12, 7]

[[12, 7, 4]]

29-30

7

Right subtree

None

4

[12, 7]

[[12, 7, 4]]

34

-

Backtracking

7

11

[12]

[[12, 7, 4]]

29-30

12

Right subtree

1

11

[12, 1]

[[12, 7, 4]]

26-27

1

Left subtree

10

10

[12, 1, 10]

[[12, 7, 4]]

22-23

1

-

10

10

[12, 1, 10]

[[12, 7, 4], [12, 1, 10]]

34

-

Backtracking

10

10

[12, 1]

[[12, 7, 4], [12, 1, 10]]

29-30

1

Right subtree

5

10

[12, 1, 5]

[[12, 7, 4], [12, 1, 10]]

26-27

5

Left subtree

None

5

[12, 1, 5]

[[12, 7, 4], [12, 1, 10]]

29-30

5

Right subtree

None

5

[12, 1, 5]

[[12, 7, 4], [12, 1, 10]]

34

-

Backtracking

5

10

[12, 1]

[[12, 7, 4], [12, 1, 10]]

34

-

Backtracking

1

11

[12]

[[12, 7, 4], [12, 1, 10]]

34

-

Backtracking

12

23

[ ]

[[12, 7, 4], [12, 1, 10]]

Sample input #2

root = TreeNode(10)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(1)
required_sum: 15

    _ 10 _ 
   |      |
   3   __ 4  
      |       
      1

We’ll start our path search from the root of our tree.

Line number

current root

Recursive call

currentNode

required_sum

currentPath

allPaths

45

10

-

-

15

-

-

14-19

10

-

10

15

[10]

[ ]

26-27

10

Left subtree

3

5

[10, 3]

[ ]

26-27

3

Left subtree

None

2

[10, 3]

[ ]

29-30

3

Right subtree

None

2

[10, 3]

[ ]

34

-

Backtracking

3

5

[10]

[ ]

29-30

10

Right subtree

4

5

[10, 4]

[ ]

26-27

4

Left subtree

1

1

[10, 4, 1]

[ ]

22-23

4

-

1

1

[10, 4, 1]

[[10, 4, 1]]

34

-

Backtracking

1

1

[10, 4]

[[10, 4, 1]]

29-30

4

Right subtree

None

1

[10, 4]

[[10, 4, 1]]

34

-

Backtracking

4

5

[10]

[[10, 4, 1]]

34

-

Backtracking

10

15

[ ]

[[10, 4, 1]]

Trace generation

The output of the following code shows the traces generated via print statements.

Note: draw_node and display_tree methods aid in visualizing the tree structure. The students can be encouraged to write these methods themselves. They don’t affect the code execution.

Press + to interact
Python 3.5
tab = 0
def height(node):
	if (node == None):
		return 0
	return 1 + max(height(node.left), height(node.right))
def draw_node(output, link_above, node, level, p, link_char):
	if (node == None): 
 		return
	out = "["
	h = len(output)
	SP = " "
	if (p < 0):
		for s in output:
			if (s):
				s = " "*(-1*p) + s
    
		for s in link_above:
			if (s):
				s = " "*(-1*p) + s
	if level < h - 1:
		p = max(p, len(output[level + 1]))
	if (level > 0):
		p = max(p, len(output[level - 1]))
	p = max(p, len(output[level]))
	# Fill in to left
	if (node.left):
		leftData = SP + str(node.left.val) + SP
		draw_node(output, link_above, node.left, level + 1, p - len(leftData),'L')
		p = max(p, len(output[level + 1]))
	# Enter this data
	space = p - len(output[level])
	if (space > 0):
		output[level] += (' ' * space)
	node_data = SP + str(node.val) + SP
	output[level] += node_data
	# Add vertical link above
	space = p + len(SP) - len(link_above[level])
	if (space > 0):
		link_above[level] += (' ' * space)
	link_above[level] += link_char
	# Fill in to right
	if (node.right):
		draw_node(output, link_above, node.right, level + 1, len(output[level]),'R')
  
def display_tree(root):
	if (root == None):
		print("\tNone")
	h = height(root)
	output = []
	link_above = []
	for i in range(0,h): 
				output.append("")
				link_above.append("")
	draw_node(output, link_above, root, 0, 5, ' ')
	# Create link lines
	for i in range(h):
		for j in range(len(link_above[i])):
			if (link_above[i][j] != ' '):
				size = len(output[i - 1])
				if (size < j + 1):
					output[i - 1] += " " *(j + 1 - size)
				jj = j
				if (link_above[i][j] == 'L'):
					while (output[i - 1][jj] == ' '):
						jj += 1
					for k in range(j+1, jj-1):
						str1 = output[i - 1]
						list1 = list(str1)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
				elif(link_above[i][j] == 'R'):
					while (output[i - 1][jj] == ' '):
						jj-=1
					
					# k = j-1
					for k in range(j-1,jj+1,-1):
						temp = output[i - 1]
						list1 = list(temp)
						list1[k] = '_'
						output[i - 1] = ''.join(list1)
						k = k - 1
      
				str1 = link_above[i]
				list1 = list(str1)
				list1[j] = '|'
				link_above[i] = ''.join(list1)
					
	# Output
	for i in range(h):
		if (i):
			print("\t" , link_above[i])
		print("\t" , output[i])
class TreeNode:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
def find_paths(root, required_sum):
  allPaths = []
  find_paths_recursive(root, required_sum, [], allPaths)
  return allPaths
def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
  global tab
  tab += 1
  if currentNode is None:
    return
  print(tab*"\t" + "Required sum: ", required_sum)
  # add the current node to the path
  currentPath.append(currentNode.val)
  print(tab*"\t" + "Appending currentNode ",currentNode.val," to the path: ", currentPath, sep = "")
  print("")
  # if the current node is a leaf and its value is equal to required_sum, save the current path
  if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
    allPaths.append(list(currentPath))
    print(tab*"\t" + "currentNode is a leaf node and its value = required_sum, ", currentNode.val, " = ",required_sum, sep = "") 
    print(tab*"\t" +"\tPath found ---> appending to allPaths: ", allPaths, sep = "")
    print("")
  else:
    # traverse the left sub-tree
    print(tab*"\t" + "Recursive call to the left sub-tree of node ", currentNode.val)
    print(tab*"\t" +"\tSubtracting currentNode value from required_sum: ", required_sum, " - ", currentNode.val)
    find_paths_recursive(currentNode.left, required_sum -
                         currentNode.val, currentPath, allPaths)
    # traverse the right sub-tree
    print(tab*"\t" +"Recursive call to the right sub-tree of node ", currentNode.val)
    find_paths_recursive(currentNode.right, required_sum -
                         currentNode.val, currentPath, allPaths)
    tab -=1
  # remove the current node from the path to backtrack,
  # we need to remove the current node while we are going up the recursive call stack.
  print(tab*"\t" + "Backtracking since all children have been visited")
  del currentPath[-1]
  print(tab*"\t" + "\tAfter removing current node from the path --->",currentPath )
  print("")
  tab -=1
def main():
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.left.left = TreeNode(4)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  required_sum = 23
  root2 = TreeNode(10)
  root2.left = TreeNode(3)
  root2.right = TreeNode(4)
  root2.right.left = TreeNode(1)
  required_sum2 = 15
  input = [[root, required_sum], [root2, required_sum2]]
  for i in input:
    print("Input tree: ")
    display_tree(i[0])
    print("")
    print("Tree paths with required_sum " , str(i[1]),
        ": " , str(find_paths(i[0], i[1])), sep = "")
    print(("-"*100)+"\n")
    global tab
    tab = 0
main()