Example
In this binary search tree,

Sample implementations
preorder(node)
print node.value
if node.left ≠ null then preorder(node.left)
if node.right ≠ null then preorder(node.right)
inorder(node)
if node.left ≠ null then inorder(node.left)
print node.value
if node.right ≠ null then inorder(node.right)
postorder(node)
if node.left ≠ null then postorder(node.left)
if node.right ≠ null then postorder(node.right)
print node.value
All sample implementations will require stack space proportional to the height of the tree. In a poorly balanced tree, this can be quite considerable.
We can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree. In the case of using threads, this will allow for greatly improved inorder traversal, although retrieving the parent node required for preorder and postorder traversal will be slower than a simple stack based algorithm.
if you want to view the edges b/w parent and its childs , simply save this image and view it in any image viewer
ReplyDelete