Home
How to Get All Binary Tree Paths in C/C++?
Tags:, , , , , , , ,

How to Get All Binary Tree Paths in C/C++?

April 17, 2016 No Comments algorithms, c / c++, coding exercise, leetcode online judge

Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Almost every tree puzzles have both iterative and recursion solutions.

Recursion

The key is decide how to pass along the path along the recursion. You may need a helper function:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root, string prev) {
        vector<string> r;
        if (root == NULL) {
            return r;
        }
        string next;
        if (prev != "") {
            next = prev + "->";
        } else {
            next = "";
        }
        if (root->left != NULL) { // all left sub paths
            auto x = binaryTreePaths(root->left, next + to_string(root->val));
            r.insert(r.end(), x.begin(), x.end());
        }
        if (root->right != NULL) { // all right sub paths
            auto x = binaryTreePaths(root->right, next + to_string(root->val));
            r.insert(r.end(), x.begin(), x.end());
        }
        if (root->left == NULL && root->right == NULL) { // leaf node
            r.push_back(next + to_string(root->val)); 
        }
        return r;
    }
 
    vector<string> binaryTreePaths(TreeNode* root) {
        return binaryTreePaths(root, "");
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root, string prev) {
        vector<string> r;
        if (root == NULL) {
            return r;
        }
        string next;
        if (prev != "") {
            next = prev + "->";
        } else {
            next = "";
        }
        if (root->left != NULL) { // all left sub paths
            auto x = binaryTreePaths(root->left, next + to_string(root->val));
            r.insert(r.end(), x.begin(), x.end());
        }
        if (root->right != NULL) { // all right sub paths
            auto x = binaryTreePaths(root->right, next + to_string(root->val));
            r.insert(r.end(), x.begin(), x.end());
        }
        if (root->left == NULL && root->right == NULL) { // leaf node
            r.push_back(next + to_string(root->val)); 
        }
        return r;
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        return binaryTreePaths(root, "");
    }
};

The good thing about this solution is that we can use vector.insert to append the recursive results e.g. left and right sub trees. We can also do this without helper function, but require appending the vector one by one (adding the -> prefix).

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
26

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> r;
        if (root == NULL) {
            return r;
        }
        if ((root->left == NULL) && (root->right == NULL)) {
            r.push_back(to_string(root->val) + "");
            return r;
        }
        if (root->left != NULL) {
            auto x = binaryTreePaths(root->left);
            for (int i = 0; i < x.size(); i ++) {
                r.push_back(to_string(root->val) + "->" + x[i]);
            }
        }
        if (root->right != NULL) {
            auto x = binaryTreePaths(root->right);
            for (int i = 0; i < x.size(); i ++) {
                r.push_back(to_string(root->val) + "->" + x[i]);
            }
        }
        return r;        
    }
};
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> r;
        if (root == NULL) {
            return r;
        }
        if ((root->left == NULL) && (root->right == NULL)) {
            r.push_back(to_string(root->val) + "");
            return r;
        }
        if (root->left != NULL) {
            auto x = binaryTreePaths(root->left);
            for (int i = 0; i < x.size(); i ++) {
                r.push_back(to_string(root->val) + "->" + x[i]);
            }
        }
        if (root->right != NULL) {
            auto x = binaryTreePaths(root->right);
            for (int i = 0; i < x.size(); i ++) {
                r.push_back(to_string(root->val) + "->" + x[i]);
            }
        }
        return r;        
    }
};

If you don’t like appending vector to vector, you can pass the result vector as a reference and append each result directly using the reference. This might be faster because there is no need to insert vector at the end of another vector.

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
26
27
28
29

class Solution {
public:
    void binaryTreePaths(TreeNode* root, string prev, vector<string> &r) {
        if (root == NULL) {
            return;
        }
        string next;
        if (prev != "") {
            next = prev + "->";
        } else {
            next = "";
        }
        if (root->left != NULL) { // go left
            binaryTreePaths(root->left, next + to_string(root->val), r);
        }
        if (root->right != NULL) { // go right
            binaryTreePaths(root->right, next + to_string(root->val), r);
        }
        if (root->left == NULL && root->right == NULL) {
            r.push_back(next + to_string(root->val)); // adding the path to the result
        }
    }
 
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> r;
        binaryTreePaths(root, "", r);
        return r;
    }
};
class Solution {
public:
    void binaryTreePaths(TreeNode* root, string prev, vector<string> &r) {
        if (root == NULL) {
            return;
        }
        string next;
        if (prev != "") {
            next = prev + "->";
        } else {
            next = "";
        }
        if (root->left != NULL) { // go left
            binaryTreePaths(root->left, next + to_string(root->val), r);
        }
        if (root->right != NULL) { // go right
            binaryTreePaths(root->right, next + to_string(root->val), r);
        }
        if (root->left == NULL && root->right == NULL) {
            r.push_back(next + to_string(root->val)); // adding the path to the result
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> r;
        binaryTreePaths(root, "", r);
        return r;
    }
};

Iteration BFS

Breadth First Search the tree and check if current node is a leaf node. 

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
26

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> r;
        if (root == NULL) {
            return r;
        }
        queue<pair<TreeNode*, string>> q;
        q.push(make_pair(root, to_string(root->val)));
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            TreeNode* cur = p.first;
            string prev = p.second;
            if ((cur->left == NULL) && (cur->right == NULL)) {
                r.push_back(prev);
            }
            if (cur->left != NULL) { /// push left
                q.push(make_pair(cur->left, prev + "->" + to_string(cur->left->val)));
            }
            if (cur->right != NULL) { /// push right
                q.push(make_pair(cur->right, prev + "->" + to_string(cur->right->val)));
            }
        }
    }
};
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> r;
        if (root == NULL) {
            return r;
        }
        queue<pair<TreeNode*, string>> q;
        q.push(make_pair(root, to_string(root->val)));
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            TreeNode* cur = p.first;
            string prev = p.second;
            if ((cur->left == NULL) && (cur->right == NULL)) {
                r.push_back(prev);
            }
            if (cur->left != NULL) { /// push left
                q.push(make_pair(cur->left, prev + "->" + to_string(cur->left->val)));
            }
            if (cur->right != NULL) { /// push right
                q.push(make_pair(cur->right, prev + "->" + to_string(cur->right->val)));
            }
        }
    }
};

In fact, if you change the data-type from queue to stack, the above solution still works. And this actually gives the following DFS solution.

Iterative DFS

Depth First Search works like recursion where the left sub trees are first explored. The traversal will go as left as possible, then explore the right subtrees before rewinding to the parent nodes.

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
26

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> r;
        if (root == NULL) {
            return r;
        }
        stack<pair<TreeNode*, string>> st;
        st.push(make_pair(root, to_string(root->val)));
        while (!st.empty()) {
            auto p = st.top();
            st.pop();
            if ((p.first->left == NULL) && (p.first->right == NULL)) {
                r.push_back(p.second);
            } else {
                if (p.first->left != NULL) { // push left
                    st.push(make_pair(p.first->left, p.second + "->" + to_string(p.first->left->val)));
                }
                if (p.first->right != NULL) { // push right
                    st.push(make_pair(p.first->right, p.second + "->" + to_string(p.first->right->val)));
                }
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> r;
        if (root == NULL) {
            return r;
        }
        stack<pair<TreeNode*, string>> st;
        st.push(make_pair(root, to_string(root->val)));
        while (!st.empty()) {
            auto p = st.top();
            st.pop();
            if ((p.first->left == NULL) && (p.first->right == NULL)) {
                r.push_back(p.second);
            } else {
                if (p.first->left != NULL) { // push left
                    st.push(make_pair(p.first->left, p.second + "->" + to_string(p.first->left->val)));
                }
                if (p.first->right != NULL) { // push right
                    st.push(make_pair(p.first->right, p.second + "->" + to_string(p.first->right->val)));
                }
            }
        }
        return r;
    }
};

C++ 11 provides std::to_string() which converts easily the integer type to string type.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
949 words
Last Post: How to Do Binary Tree Inorder Traversal in C/C++?
Next Post: Algorithm to Determine the Best Time to Buy and Sell Stock

The Permanent URL is: How to Get All Binary Tree Paths in C/C++?

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  3. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  4. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  5. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...
  6. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...
  7. Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary search tree (BST),...
  8. How to Find the Kth Smallest Element in a BST Tree Using Java/C++? Given a binary search tree, write a function kthSmallest to find the kth smallest element...

Leave a Reply