The four different traversals of T are In order, Post order, Preorder and Level-by-level traversal.
Each operator node has exactly two branches
Each operand node has no branches, such trees are called expression trees.
A + B * C - D * E
What is the logic behind in order traversal? (This is for interviewee)
In this traversal, if tree is not empty, we first traverse (in order) the left sub tree; then visit the root node of tree, and then traverse (in order) the right sub tree.
A B C * + D E * -
Logic behind traversal: First traverse left(T) (in post order); then traverse Right(T) (in post order); and finally visit root.
Strategy: Left-Right-Root strategy, i.e.
Traverse the left sub tree In Post order
Traverse the right sub tree in Post order.P Visit the root.
Logic: Visit root first; then recursively perform preorder traversal of Left(T); followed by pre order. traversal of Right(T)
Visit the root
Traverse the left sub tree preorder.
Traverse the right sub tree preorder.