ansaurus

Question

Answer 1

+2 A:

The following pseudo-code will do what you want for a tree in ascending order.

def findval (node,lookfor):
    if node is null:
        return null
    if node.val is equal to lookfor:
        return node
    if node.val is less than lookfor
        return findval (node.right,lookfor)
    return findval (node.left,lookfor)

to be called with:

znode = findval (root, "z")

It will give you the node or null if no node exists.

Obviously, there's all sorts of enhancements you could make such as allowing a different order, or a callback comparison function, or allowing duplicate keys, but this is the canonical example of a binary tree search.

paxdiablo 2010-10-27 22:50:02

this solution assumes that the right node has values greater than the left node, but my question does not say that.

fmunshi 2010-10-27 22:53:37

But that invariably is the case because such trees are created as search structures. If it is not the case, then you need a depth first or breadth first search.

winwaed 2010-10-27 22:54:58

The usual behaviour of a binary tree is ascending order. If that's not the case, simply switch around the conditions.

paxdiablo 2010-10-27 22:55:29

@fmunshi, the whole point of a tree is to order the nodes. It's a reasonable assumption to make that the children would be ordered.

Mark Ransom 2010-10-27 22:57:38

what is the reason for putting the check for node being NULL at the beginning?

fmunshi 2010-10-27 23:07:09

@fmunshi, that's so it can elegantly handle an empty tree (where root is null).

paxdiablo 2010-10-27 23:37:59

ansaurus

tags:

views:

answers:

Pseudo-code for search in binary tree

related questions