Finding an item in a Binary Tree

Useful video - recursive
resource - non recursive

So, we have a binary tree of Nodes. Each node has data and 2 pointers, a left pointer and a right pointer.

 

Diagramatically, we can represent a binary tree as follows:

 

How would we find an item in a binary tree?

Let's consider this in structured English:

  1. SET current node index to root node
  2. INPUT search item
  3. WHILE the seach item is not the same as the data in the current node and the current node index is not NULL, DO the following:
  4. IF the search item is less than the data at the searchPointer, update the current node index to be the left pointer of the current node
  5. IF the search item is greater than the data at the searchPointer, update the current node index to be the left pointer of the current node
  6. After looping, IF current node index is NULL, OUTPUT "Not found", otherwise OUTPUT the data item and the current node index.

PSEUDOCODE - fill the blanks

Note: each Node in the array/tree has 3 attributes: data, leftPointer and rightPointer

DECLARE tree: ARRAY[0:X] OF Node

DECLARE rootPointer, searchPointer, searchItem : INTEGER

← 0

searchPointer ← rootPointer

INPUT

WHILE tree[searchPointer].data <> searchITEM AND searchPointer <> -1 //or NULL

IF > searchItem THEN

searchPointer ←

ELSE

searchPointer ←

ENDIF

END WHILE

IF searchPointer = THEN

OUTPUT "ITEM NOT FOUND"

ELSE

OUTPUT searchPointer

END IF

   

This unit requires you to create an evidence document.

Tags

data type INTEGER pseudocode REAL program code DATE STRING CHAR bubble sort BOOLEAN declare variable