Jerry's Notes

Binary Tree Traversal

Binary Tree
Word count: 753Reading time: 4 min
2022/01/14

Binary Tree Traversal

We should handle at least 2 approaches: recursion and iteration.

Preorder

  1. Binary Tree Preorder Traversal
    https://leetcode.com/problems/binary-tree-preorder-traversal/

Recursion

  1. Save root node value
  2. Call recursion on the left children
  3. Call recursion on the right children
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal (TreeNode* root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
    void preorder (TreeNode* root, vector<int>& res) {
        if (!root) return;
        res.push_back(root->val);
        if (root->left) preorder(root->left, res);
        if (root->right) preorder(root->right, res);
    }
};

Interation

  1. Push root into stack, and save its value
  2. Move pointer to its left node
  3. when pointer is null, means that the node don’t have left child, then back to the top of the stack, move pointer to its right child
  4. Repeat 1-3 until stack or pointer is empty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> preorderTraversal (TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* p = root;
        while (!stk.empty() || p) {
            while (p) {
                stk.push(p);
                res.push_back(p->val);
                p = p->left;
            }
            p = stk.top();
            stk.pop();
            p = p->right;
        }
        return res;
    }
};

Inorder

  1. Binary Tree Inorder Traversal
    https://leetcode.com/problems/binary-tree-inorder-traversal/

Recursion

  1. Call recursion on the left child
  2. Push root node value
  3. Call recursion on the right child
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) return;
        if (root->left) inorder(root->left, res);
        res.push_back(root->val);
        if (root->right) inorder(root->right, res);
    }
};

Iteration

  1. Push root into stack
  2. Push all left children into stack
  3. Remove the top node from the stack, save node value
  4. Move current pointer to the right child of current node
  5. If contain right child, push all left children into 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
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        // 1. push root into stack
        stk.push(root);
        TreeNode* p = root;
        while (p || !stk.empty()) {
            // 2. push all left children into stack
            while (p) {
                stk.push(p);
                p->left;
            }
            // 3. save top of the stack
            p = stk.top();
            stk.pop();
            res.push_back(p->val);
            // 4. point to right child
            p->right;
        }
        return res;
    }
};

Postorder

  1. Binary Tree Postorder Traversal
    https://leetcode.com/problems/binary-tree-postorder-traversal/

Recursion

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }
    void postorder(TreeNode* root, vector<int>& res) {
        if (!root) return;
        if (root->left) postorder(root->left, res);
        if (root->right) postorder(root->right, res);
        res.push_back(root->val);
    }
};

Iteration

The pointer movement order is: root -> right -> left, push corresponding value to the begining of the res, then the order in res becomes: left -> right -> root.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode *p = root;
        while (!stk.empty() || p) {
            while (p) {
                stk.push(p);
                res.insert(res.begin(), p->val);
                p = p->right;
            }
            TreeNode *t = stk.top(); 
            stk.pop();
            p = t->left;
        }
        return res;
    }
};
Total : 15
2022
Sliding Window BST Dynamic Programming Research Project DFS Permutations Binary Tree Sort BFS love-letter
LeetCode Algorithms for Sensor-Based Robotics Rambling Digression