Algorithm to Follow the Instructions to Traversal a Binary Tree

You are given a tree root and a list of strings moves consisting of “RIGHT”, “LEFT” and “UP”. Starting from root, traverse the tree by performing each move in moves where:

“RIGHT” means to traverse to the right child.
“LEFT” means to traverse to the left child.
“UP” means to traverse to its parent.
Return the value of the last node after all moves. You can assume that the moves are valid.

For example, given root:

   9
  / \
 1   8
    / \
   6   0
  / \
 3   2

And moves = [“RIGHT”, “RIGHT”, “UP”, “LEFT”, “RIGHT”], return 2.

Example 1
Input
root = [0, null, [1, null, null]]
moves = [“RIGHT”]
Output
1

Traversal the Binary Tree using a Stack

The key to solve the problem is to use a stack to store the parent nodes when we go down the left or right branch. If a “UP” is invoked, then we have to pop and return the top of the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int solve(Tree* root, vector<string>& moves) {
    stack<Tree*> st;
    st.push(root);
    for (const auto &n: moves) {
        if (n == "RIGHT") {
            st.push(root->right);
            root = root->right;
        } else if (n == "LEFT") {
            st.push(root->left);
            root = root->left;
        } else if (n == "UP") {
            st.pop();
            root = st.top();
        }
    }
    return root->val;
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int solve(Tree* root, vector<string>& moves) {
    stack<Tree*> st;
    st.push(root);
    for (const auto &n: moves) {
        if (n == "RIGHT") {
            st.push(root->right);
            root = root->right;
        } else if (n == "LEFT") {
            st.push(root->left);
            root = root->left;
        } else if (n == "UP") {
            st.pop();
            root = st.top();
        }
    }
    return root->val;
}

The time complexity is O(N) where N is the number of the instrutions and the space requirement is O(N) where N is the number of the nodes in the binary tree.

–EOF (The Ultimate Computing & Technology Blog) —