loops search binary-search-tree binary-search pseudocode

Pseudocode - Search Tree

I need some help with the following problem. There is a Search Tree (Binary Search Tree) and I need to find a particular element, so to search the Search Tree. But this only needs to be displayed in Pseudocode (so the actual search tree isn't needed, so just for an example the root is 75 and the element that needs to be searched is 24).

So for example step 1: Print Root, 2: Print Tree....(until the correct element has been found).

I have done this so far:

1) def findval (node, lookForElement):
2) while node is not null:
3) if node.val is equal to lookForElement:
4) break
5) if node.val is less than lookForElement:
6) node = node.right
7) else:
8) node = node.left
9) return node 10) if node is null: 11) print "tree is empty"

But I think this would only work if the the searched element is the next element down, but the searched element could be a few branches down so therefore how would I correctly loop?

Solution

Your algorithm to find the node is pretty much correct:

DEF FINDVAL(search)
  LET node = root
  WHILE node != null
    PRINT_ELEMENTS(node)
    IF node.value == search
      BREAK
    ELSE IF node.value < search
      node = node.right
    ELSE
      node = node.left

  RETURN node

The indentation and the space makes it much clearer that the return statement should be outside the WHILE loop. You can only reach it by breaking out of the loop, which happens when you have found the search value (hooray!), or when node becomes null. If node is null, then our desired value is not in the tree.

With the following tree:

      75
    /    \
   18    88
  /  \     \
 6   24    90

The FINDVAL algorithm will display the following:

6, 18, 24, 75, 88, 90
6, 18, 24
24

UPDATE: To insert a new value, if it doesn't already exist:

DEF INSERTVAL(value)
  LET node = root
  WHILE node != null
    PRINT_ELEMENTS(node)
    IF node.value == value
      PRINT("Value already exists")
      RETURN
    ELSE IF node.value < value
      IF node.right == null
        node.right = new Node(value)
        RETURN
      node = node.right
    ELSE
      IF node.left == null
        node.left = new Node(value)
        RETURN
      node = node.left

  root = new Node(value)

This psuedocode may seem a bit harder to understand, because we have to look at two layers in the tree at a time, instead of one. We look at the parent, decide whether to go left or right, and then if that direction is null we insert the new value. If it is not null, we move on to that node and repeat.

Now, the only way to exit the while loop is still by 'node' being null, or by us returning from within the loop. But within the loop, every time we move down a node, first we check if it is null, and we insert and return if it is. So the only time the value of 'node' can be null is if the root is null.