KEMBAR78
Searching A Tree | PDF | Theoretical Computer Science | Graph Theory
Scribd
Upload
44 views14 pages

Searching A Tree

The document describes different search algorithms for traversing tree data structures, including depth-first search (DFS) and breadth-first search (BFS). DFS involves exploring nodes along one path until reaching a leaf, then backtracking, while BFS explores all nodes at each level from the root before moving to the next level. Pseudocode is provided for DFS and BFS algorithms to search for a contained value or find the path to a target node. The document also discusses an optimized DFS for ordered trees.

Uploaded by

Dilan Srilal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
44 views14 pages

Searching A Tree

The document describes different search algorithms for traversing tree data structures, including depth-first search (DFS) and breadth-first search (BFS). DFS involves exploring nodes along one path until reaching a leaf, then backtracking, while BFS explores all nodes at each level from the root before moving to the next level. Pseudocode is provided for DFS and BFS algorithms to search for a contained value or find the path to a target node. The document also discusses an optimized DFS for ordered trees.

Uploaded by

Dilan Srilal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

Searching a tree

Imagine we want to examine a tree


To determine if an element is present
To find a path to a solution point
To make a series of decisions to reach some
objective

Searching a tree
Depth first search
Start with the root
At any node, if we havent reached our objective, take
the left branch first
When get to a leaf, backtrack to the first decision
point and take the right branch

Breadth first search


Start with the root
Then proceed to each child at the next level, in order
Continue until reach objective

Depth first search


5
2

Breadth first search


5
2

Depth first search for containment


Idea is to keep a data structure (called a stack)
that holds nodes still to be explored
Use an evaluation function to determine when
reach objective (i.e. for containment, whether
value of node is equal to desired value)
Start with the root node
Then add children, if any, to front of data
structure, with left branch first
Continue in this manner

DFS code
def DFSBinary(root, fcn):
stack= [root]
while len(stack) > 0:
if fcn(stack[0]):
return True
else:
temp = stack.pop(0)
if temp.getRightBranch():
stack.insert(0,
temp.getRightBranch())
if temp.getLeftBranch():
stack.insert(0,
temp.getLeftBranch())
return False

Depth first search


5
2

1
5

3, 8

2, 8

1, 4, 8

4, 8

BFS code
Def BFSBinary(root, fcn):
queue = [root]
while len(queue) > 0:
if fcn(queue[0]):
return True
else:
temp = queue.pop(0)
if temp.getLeftBranch():
queue.append(temp.getLeftBranch())
if temp.getRightBranch():
queue.append(temp.getRightBranch())
return False

Breadth first search


5
2

1
5

4, 6

2, 8

6, 3

8, 1, 4
1, 4, 6

Depth first search for path


Suppose we want to find the actual path from
root node to desired node
A simple change in the code lets us trace back
up the tree, once we find the desired node

DFS code
def DFSBinaryPath(root, fcn):
stack= [root]
while len(stack) > 0:
if fcn(stack[0]):
return TracePath(stack[0])
else:
temp = stack.pop(0)
if temp.getRightBranch():
stack.insert(0, temp.getRightBranch())
if temp.getLeftBranch():
stack.insert(0, temp.getLeftBranch())
return False
def TracePath(node):
if not node.getParent():
return [node]
else:
return [node] + TracePath(node.getParent())

Ordered search
Suppose we know that the tree is ordered,
meaning that for any node, all the nodes to
the left are less than that nodes value, and
all the nodes to the right are greater than
that nodes value

DFS code
def DFSBinaryOrdered(root, fcn, ltFcn):
stack= [root]
while len(stack) > 0:
if fcn(stack[0]):
return True
elif ltFcn(stack[0]):
temp = stack.pop(0)
if temp.getLeftBranch():
stack.insert(0,
temp.getLeftBranch())
else:
if temp.getRightBranch():
stack.insert(0,
temp.getRightBranch())
return False

Depth first ordered search


5
2

5
8
6

You might also like