Binary Tree Information

Binary search tree: (Copied from Wiki)

Depth-first

• Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)
• Inorder traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right); note how this produces a sorted sequence
• Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)

Breadth-first

• Level-order traversal sequence: F, B, G, A, D, I, C, E, H

pre-order	in-order	post-order	level-order
push F pop F push G B pop B push D A pop A pop D push E C pop C pop E pop G push I pop I push H pop H	push F B A pop A pop B push D C pop C pop D push E pop E pop F push G pop G push I H pop H pop I	push F B A pop A push D C pop C push E pop E pop D pop B push G I H pop H pop I pop G pop F	enqueue F dequeue F enqueue B G dequeue B enqueue A D dequeue G enqueue I dequeue A dequeue D enqueue C E dequeue I enqueue H dequeue C dequeue E dequeue H

[edit]Sample implementations

preorder(node)
  if node = null then return
  print node.value
  preorder(node.left) 
  preorder(node.right)

inorder(node)
  if node = null then return
  inorder(node.left)
  print node.value
  inorder(node.right)

postorder(node)
  if node = null then return
  postorder(node.left)
  postorder(node.right)
  print node.value

Power Point Representation