Home/

...

/

Introduction

Introduction

Real-world Problems

The following are a few real-world problems that can be solved using the Breadth-First Search pattern.

Traversing DOM Tree I

We need to figure out a way to traverse the DOM structure that we obtain from a single web page. The HTML can be represented in a tree structure where the children of the HTML tag become the children of a node in the tree. Each tree level can have any number of nodes depending upon the number of nested HTML tags. We need to traverse the nodes in the tree level by level, starting at the root node.

<body>

  <nav>

    <a>About</a>

  </nav>

  <p>Paragraph</p>

</body>
DOM Tree

The root node, in our case, will be the body tag. This root node will have the complete web page nested within its children. We have to return the values of each levels’ nodes from left to right in separate subarrays. This way, we can separately analyze their content for further data processing.

Let’s try to understand this better with an illustration:

Traversing DOM Tree II

The number of web pages can be enormous, and traversing all of them will consume a lot of space. So, we need a more space-efficient method to traverse the DOM tree. Therefore, we have come up with a better approach in which we create a shadow tree for the DOM where each node has a pointer to the next node to its right on the same level. We’ll introduce an additional attribute, next, to our TreeNode structure. The next node will point to its immediate right node on the same level. If there is no right node to point, next will point to null. This next pointer will allow us to avoid the queue data structure that we used previously to traverse the tree, resulting in a space-efficient approach.

The root node, in our case, will again be the body tag. This root node will have the complete web page nested within its children. We have to go through each node and assign the next pointer to the node to its immediate right on the same level.

Let’s try to understand this better with an illustration:

Dry-run templates

The following is the implementation of the solution provided for the Minimum Depth of a Binary Tree (easy) problem:

Press + to interact
Python 3.5
from collections import deque
class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right = None, None
def find_minimum_depth(root):
  if root is None:
    return 0
  queue = deque()
  queue.append(root)
  minimumTreeDepth = 0
  while queue:
    minimumTreeDepth += 1
    levelSize = len(queue)
    for _ in range(levelSize):
      currentNode = queue.popleft()
      # check if this is a leaf node
      if not currentNode.left and not currentNode.right:
        return minimumTreeDepth
      # insert the children of current node in the queue
      if currentNode.left:
        queue.append(currentNode.left)
      if currentNode.right:
        queue.append(currentNode.right)
def main():
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  print("Tree Minimum Depth: " + str(find_minimum_depth(root)))
  root.left.left = TreeNode(9)
  root.right.left.left = TreeNode(11)
  print("Tree Minimum Depth: " + str(find_minimum_depth(root)))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
       root.right.left = TreeNode(10)
       root.right.left.left = TreeNode(11)
       root.right.right = TreeNode(5)
  root.left.left = TreeNode(9)

#Visual representation of the tree is as follows

      _ 12 __ 
     |       |
   _ 7    __ 1 _ 
  |      |      |
  9   __ 10     5 
     |
     11

Iteration No.

Line No.

deque

levelSize

currentNode

minimumTreeDepth

-

15-16

[12]

-

-

0

1

18-19

[12]

1

-

1

1

21

[]

1

12

1

1

28-31

[7,1]

1

12

1

2

18-19

[7,1]

2

12

2

1

21

[1]

2

7

2

1

28-31

[1,9]

2

7

2

2

21

[9]

2

1

2

2

28-31

[9,10,5]

2

1

2

3

18-19

[9,10,5]

3

1

3

3

21

[10,5]

3

9

3

Sample Input 2

root = TreeNode(1)
  root.left = TreeNode(2)
       root.left.left = TreeNode(3)
       root.left.right = TreeNode(3)
  root.right = TreeNode(2)
       root.right.left = TreeNode(4)
       root.right.right = TreeNode(4)

#Visual representation of the tree is as follows: 

      _ 1 ____ 
     |        |
   _ 2 _    _ 2 _ 
  |     |  |     |
  3     3  4     4

Students may be encouraged to complete the dry-run with this input:

Iteration No.

Line No.

deque

levelSize

currentNode

minimumTreeDepth

-

15-16

[1]

-

-

0

1

18-19

[1]

1

-

1

1

21

[]

1

1

1

1

28-31

[2,2]

1

1

1

...

...

...

...

...

...

Trace Generation

The output of the following code shows the traces generated via print statements. Note the draw_node and display_tree methods. These methods allow the learner to see the input data more clearly. An interesting challenge could be to encourage students to write these methods themselves.

Press + to interact
Python 3.5
from collections import deque
class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right = None, None
  def __repr__(self):
    return str(self.val)
def find_minimum_depth(root):
  if root is None:
    return 0
  queue = deque()
  queue.append(root)
  minimumTreeDepth = 0
  iteration = 0
  while queue:
    print("\tIteration: ", iteration+1)
    iteration += 1 
    print("\t\tQueue", queue)
    minimumTreeDepth += 1
    print("\t\tminimumTreeDepth",minimumTreeDepth)
    levelSize = len(queue)
    for _ in range(levelSize):
      currentNode = queue.popleft()
      print("\t\t\tcurrentNode: ",currentNode)
      # check if this is a leaf node
      if not currentNode.left and not currentNode.right:
        print("\t\t\tFirst leaf node found... return minimumTreeDepth: ",minimumTreeDepth)
        return minimumTreeDepth
      # insert the children of current node in the queue
      if currentNode.left:
        queue.append(currentNode.left)
      if currentNode.right:
        queue.append(currentNode.right)
      print("\t\t\tQueue after adding child nodes to it: ",queue)
	 
# Display List Code Below:
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])
def main():
  #Tree 1
  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  root.left.left = TreeNode(9)
  root.right.left.left = TreeNode(11)
  
  #Tree 2
  root2 = TreeNode(1)
  root2.left = TreeNode(2)
  root2.left.left = TreeNode(3)
  root2.left.right = TreeNode(3)
  root2.right = TreeNode(2)
  root2.right.left = TreeNode(4)
  root2.right.right = TreeNode(4)
  trees = [root,root2]
  for tree in trees:
	  print("Input Tree: ")
	  display_tree(tree)
	  print("Tree Minimum Depth: " + str(find_minimum_depth(tree)))
	  print("-"*100+"\n")
main()