Editing Tree traversal (section)

==Implementations==
{{unreferenced section|date=June 2013}}
===Depth-first search implementation===
Below are examples of [[stack (abstract data type)|stack]]-based implementation for pre-order, post-order and in-order traversal in recursive approach (left) as well as iterative approach (right).

Implementations in iterative approach are able to avoid the [[Recursion (computer science)#Recursion versus iteration|drawbacks of recursion]], particularly limitations of stack space and performance issues.

Several alternative implementations are also mentioned.

===={{anchor|Pre-order traversal code|Pre-order traversal code}}Pre-order implementation====
{|
|- style="vertical-align:top;"
|
 '''procedure''' preorder(node)
     '''if''' node = '''null'''
         '''return'''
     visit(node)
     preorder(node.left)
     preorder(node.right) 
|
 '''procedure''' iterativePreorder(node)
     '''if''' node = '''null'''
         '''return'''
     stack ← '''empty stack'''
     stack.push(node)
     '''while''' '''not''' stack.isEmpty()
         node ← stack.pop()
         visit(node)
         // right child is pushed first so that left is processed first
         '''if''' node.right ≠ '''null'''
             stack.push(node.right)
         '''if''' node.left ≠ '''null'''
             stack.push(node.left)
|}

===={{anchor|Post-order traversal code|Post-order traversal code}}Post-order implementation====
{|
|- style="vertical-align:top"
|
 '''procedure''' postorder(node)
     '''if''' node = '''null'''
         '''return'''
     postorder(node.left)
     postorder(node.right)
     visit(node)
|
 '''procedure''' iterativePostorder(node)
     '''if''' node = '''null'''
         '''return'''
     stack ← '''empty stack'''
     lastNodeVisited ← '''null'''
     '''while''' '''not''' stack.isEmpty() '''or''' node ≠ '''null'''
         '''if''' node ≠ '''null'''
             stack.push(node)
             node ← node.left
         '''else'''
             peekNode ← stack.peek()
             // if right child exists and traversing node
             // from left child, then move right
             '''if''' peekNode.right ≠ '''null''' '''and''' lastNodeVisited ≠ peekNode.right
                 node ← peekNode.right
             '''else'''
                 visit(peekNode)
                 lastNodeVisited ← stack.pop()
|}

===={{anchor|Inorder traversal code|In-order traversal code}}In-order implementation====

{|
|- style="vertical-align:top;"
|
 '''procedure''' inorder(node)
     '''if''' node = '''null'''
         '''return'''
     inorder(node.left)
     visit(node)
     inorder(node.right)
|
 '''procedure''' iterativeInorder(node)
     '''if''' node = '''null'''
         '''return'''
     stack ← '''empty stack'''
     '''while''' '''not''' stack.isEmpty() '''or''' node ≠ '''null'''
         '''if''' node ≠ '''null'''
             stack.push(node)
             node ← node.left
         '''else'''
             node ← stack.pop()
             visit(node)
             node ← node.right
|}

====Another variant of pre-order====
If the tree is represented by an array (first index is 0), it is possible to calculate the index of the next element:<ref>{{Cite web|title=constexpr tree structures|url=https://fekir.info/post/constexpr-tree/#_dfs_traversal|access-date=2021-08-15|website=Fekir's Blog|date=9 August 2021|language=en}}</ref>{{clarify|reason=Explicitly mention the restrictions on trees in order to be handled by this algorithm. Since there is no isLeaf() test, it seems that all leaves must be on maximal depth or one level above it, like in a [[heap (data structure)]].|date=November 2021}}

 '''procedure''' bubbleUp(array, i, leaf)
     k ← 1
     i ← (i - 1)/2
     '''while''' (leaf + 1) % (k * 2) ≠ k
         i ← (i - 1)/2
         k ← 2 * k
     '''return''' i
 
 '''procedure''' preorder(array)
     i ← 0
     '''while''' i ≠ array.size
         visit(array[i])
         '''if''' i = size - 1
             i ← size
         '''else if''' i < size/2
             i ← i * 2 + 1
         '''else'''
             leaf ← i - size/2
             parent ← bubble_up(array, i, leaf)
             i ← parent * 2 + 2

====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).

====Morris in-order traversal using threading====
{{main|Threaded binary tree}}
A binary tree is threaded by making every left child pointer (that would otherwise be null) point to the in-order predecessor of the node (if it exists) and every right child pointer (that would otherwise be null) point to the in-order successor of the node (if it exists).

Advantages:
# Avoids recursion, which uses a call stack and consumes memory and time.
# The node keeps a record of its parent.

Disadvantages:
# The tree is more complex.
# We can make only one traversal at a time.
# It is more prone to errors when both the children are not present and both values of nodes point to their ancestors.

Morris traversal is an implementation of in-order traversal that uses threading:<ref>{{Cite journal | doi = 10.1016/0020-0190(79)90068-1| title = Traversing binary trees simply and cheaply| journal = [[Information Processing Letters]]| volume = 9| issue = 5| year = 1979| last1 = Morris | first1 = Joseph M.| pages = 197–200}}</ref>
# Create links to the in-order successor.
# Print the data using these links.
# Revert the changes to restore original tree.

===Breadth-first search===
Also, listed below is pseudocode for a simple [[Queue (data structure)|queue]] based level-order traversal, and will require space proportional to the maximum number of nodes at a given depth. This can be as much as half the total number of nodes. A more space-efficient approach for this type of traversal can be implemented using an [[iterative deepening depth-first search]].

 '''procedure''' levelorder(node)
     queue ← '''empty queue'''
     queue.enqueue(node)
     '''while''' '''not''' queue.isEmpty()
         node ← queue.dequeue()
         visit(node)
         '''if''' node.left ≠ '''null'''
             queue.enqueue(node.left)
         '''if''' node.right ≠ '''null'''
             queue.enqueue(node.right)

If the tree is represented by an array (first index is 0), it is sufficient iterating through all elements:

 '''procedure''' levelorder(array)
     '''for''' i '''from''' 0 '''to''' array.size
         visit(array[i])