Editing Tree traversal (section)

====Advancing to the next or previous node====
The <code>node</code> to be started with may have been found in the binary search tree <code>bst</code> by means of a standard '''search''' function, which is shown here in an implementation without parent pointers, i.e. it uses a <code>stack</code> for holding the ancestor pointers.

 '''procedure''' search(bst, key)
     // returns a (node, stack)
     node ← bst.root
     stack ← '''empty stack'''
     '''while''' node ≠ '''null'''
         stack.push(node)
         '''if''' key = node.key
             '''return''' (node, stack)
         '''if''' key < node.key
             node ← node.left    
         '''else'''
             node ← node.right
     '''return''' ('''null''', '''empty stack''')

The function '''inorderNext'''<ref name="Pfaff"/>{{rp|60}} returns an in-order-neighbor of <code>node</code>, either the {{nowrap|in-order-''suc''cessor}} (for <code>dir=1</code>) or the {{nowrap|in-order-''prede''cessor}} (for <code>dir=0</code>), and the updated <code>stack</code>, so that the binary search tree may be sequentially in-order-traversed and searched in the given direction <code>dir</code> further on.

 '''procedure''' inorderNext(node, dir, stack)
     newnode ← node.child[dir]
     '''if''' newnode ≠ '''null'''
         '''do'''
             node ← newnode
             stack.push(node)
             newnode ← node.child[1-dir]
         '''until''' newnode = '''null'''
         '''return''' (node, stack)
     // node does not have a dir-child:
     '''do'''
         '''if''' stack.isEmpty()
             '''return''' ('''null''', '''empty stack''')
         oldnode ← node
         node ← stack.pop()   // parent of oldnode
     '''until''' oldnode ≠ node.child[dir]
     // now oldnode = node.child[1-dir],
     // i.e. node = ancestor (and predecessor/successor) of original node
     '''return''' (node, stack)

Note that the function does not use keys, which means that the sequential structure is completely recorded by the binary search tree’s edges. For traversals without change of direction, the ([[Amortized analysis|amortised]]) average complexity is <math>\mathcal{O}(1) ,</math> because a full traversal takes <math>2 n-2</math> steps for a BST of size <math>n ,</math> 1 step for edge up and 1 for edge down. The worst-case complexity is <math>\mathcal{O}(h) </math> with <math>h</math> as the height of the tree.

All the above implementations require stack space proportional to the height of the tree which is a [[call stack]] for the recursive and a parent (ancestor) stack for the iterative ones. In a poorly balanced tree, this can be considerable. With the iterative implementations we can remove the stack requirement by maintaining parent pointers in each node, or by [[#Morris in-order traversal using threading|threading the tree]] (next section).