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?
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', '+'
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:
(This is also called Symmetric traversal.)
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.
