Bottom up tree traversal starting from a specific leaf

Question

I am looking for a way to cross a tree from bottom to top, so that I can start with a specific sheet of my choice, and then go to the root.

Expected result: in my sample tree of samples in the link, the tree sample that was taken from here , the algorithm will return YXZWVUT if I specify starting with Y.

I would be grateful for any help with this.

Answer 1

If I understood the question correctly, it would be a statement of the problem

n- , node, , node , . node node, node node.

, TraverseUp() - , PostOrderTraversal(), . A . :

TraverseUp(Array *A, Node *n) {
  // Add n to A to maintain bottom up nature
  if (!n) return;
  A.add(n)

  // Go to parent
  Node *p = n.parent();
  if (!p) return;

  // For each child of p other than n, do a post order traversal
  foreach(Node *c in p.children) {
    if (c == n) continue;
    PostOrderTraversal(A, c);
  }
  // When done with adding all p children, continue traversing up
  TraverseUp(A, p);
}

// Standard implementation of post order traversal
PostOrderTraversal(Array *A, Node *n) {
  if (!n) return;
  foreach(Node *c in n.children) {
    PostOrderTraversal(A, c);
    A.add(c);
  }
}