how to parse a tree data structure?

Question

I have a tree data structure, comprised of nodes, that I need to parse into an expression tree. My nodes look like this (simplified):

    public class Node
    {
        public Node Left { get; set; }
        public Node Right { get; set; }
        public Operation OperationType { get; set; }
        public object Value { get; set; }
    }

What is the best / correct way to find the bottom of the tree and work backwards building up the expression tree? Do you parse left or right first?

Answer 1

I don't think it matters which direction you traverse first. However, in a world where left-to-right language dominates, someone would more intuitively understand your code if you went left first.

Answer 2

If you want to get to the bottom of the tree first, then you do an 'in-order' or perhaps 'post-order' search. An 'in-order' search will find the bottom, left-most node first, followed by the parent of that node, and then the right-hand child of the parent. A 'post-order' search will 'visit' both the left child node and the right child node before visiting the parent node.

Consider the expression 'x + y'. An in-order search would yield:

'x', '+', 'y'

whereas an post-order search would yield:

'x', 'y', '+'

Answer 3

As mentioned, it doesn't really matter where you go first. But the most usual tree traversal algorithms. If this tree is organized the way I think, inorder would be recommended:

(from wikipedia)To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node:

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

(This is also called Symmetric traversal.)