Traversing Tree

• Preorder

• Postorder

• Level order

• NOTE :The inorder traversal is the special case for binary trees.

(another definition possible) 

- inorder는 binary-tree에서만 존재한다.

 preorder traversal

– To move down the tree to the left until a null node is reached

– The null node’s parent is then “visited”, and the traversal continues with the node that is one to the right

– If there is no move to the right, the traversal continues with the last unvisited node at the next higher level of the tree 

• Vertex -> Left subtree -> Right subtree 

– Root : 1st position in traversal
– Bottom right child: latest position 

 postorder traversal

– To move down the tree to the left until a null node is reached

– The traversal continues with the null node’s parent and then to the right

– If there is no move to the right (null node), the null node’s parent is then “visited”, and the traversal continues with the node at the next higher level of tree 

• Left subtree -> Right subtree -> Vertex 

– Root: latest position in traversal
– Bottom left child: 1st position 

- EX) % rm -r /user/bit 

inorder traversal of a binary tree

– In an inorder traversal a node is visited after its left subtree and before its right subtree 

• Left subtree -> Vertex -> Right subtree
– Bottom left child : 1st position
– Bottom right child :latest position in traversal