Binary Search Trees Solutions

Document last modified:

Question

Give a tail-recursive successor.

Iterative version

Node Tree_Successor (preserves Node x )

    if x.right ≠ NIL
        return Tree_Minimum ( x.right )
    else
        Node y ← x.p
        while y ≠ NIL && x = y.right
            x ← y
            y ← y.p
        return y

Tail recursive

Node Tree_Successor ( Node x )

if x.right ≠ NIL return Tree_Minimum( x.right )

return Parent_Successor( x ) -- Successor is direct ancestor

Node Parent_Successor ( Node x )

Node y ← x.p

if y = NIL or x ≠ y.right return y.right

return Parent_Successor( y )

Give an algorithm to count the number of nodes in a binary tree.

int Tree_Nodes ( Node T )

if T = NIL return 0

return 1 + Tree_Nodes ( T.left ) + Tree_Nodes ( T.right )

Give an algorithm to count the number of leaf nodes in a tree.

int Tree_Leaves ( Node T )

if T = NIL return 0

if T.left = NIL and T.right = NIL return 1

return Tree_Leaves ( T.left ) + Tree_Leaves ( T.right )

Give an algorithm to determine the height of a tree. A tree of one node has height = 0.

int Tree_Height ( Node T )

if T = NIL return -1

return max( Tree_Height ( T.left ), Tree_Height ( T.right ) ) + 1