CODEWITHSUNDEEP
pythonalgorithmtree
user2977500
user2977500

Reputation: 157

Print all paths from Root to each leaf

For a Tree where each Node is provided with the following tuple:

(Value, LeftNode, RightNode)

How is it possible to print all value chains possible from root to each leaf?

For example: (1,(2,(4,(7,None,None),None),(5, None, None)),(3,None,(6, None,None)))

It should represent the following tree:

Example tree

The expected result is:
[1,2,4,7]
[1,2,5]
[1,3,6]

Upvotes: 1

Views: 1565

Answers (3)

user2390182
user2390182

Reputation: 73470

Here is a more readable recursive generator:

def paths(node):
    if node is None:
        return
    val, *children = node
    if any(children):
        for child in children: 
            for path in paths(child):
                yield [val] + path
    else:
        yield [val]

>>> list(paths(root))
[[1, 2, 4, 7], [1, 2, 5], [1, 3, 6]]

This has the added benefit of working for nodes with arbitrary numbers of children.

Upvotes: 2

BishalG
BishalG

Reputation: 1434

Seems like you are trying to solve this problem: https://leetcode.com/problems/binary-tree-paths/

Here, you can simply start exploring tree with dfs and store the values as you go down in tree and maintain a vector of all values from the root to the current node. As soon as you finish processing that node, simply remove the values at current node from that vector. When we reached the leaf node, we simply append the values in vector to our answer.

Here is code implemented in cpp for your refernece:

/**
* 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:
   void solve(TreeNode* root, vector<int>&values, vector<string>&ans) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        // leaf node
        string str = "";
        values.push_back(root->val);
        str += ::to_string(values[0]);
        for (int i = 1; i < values.size(); ++i) {
            str += "->";
            str += ::to_string(values[i]);
        }
        ans.push_back(str);
        values.pop_back();
        return;
    }
    values.push_back(root->val);
    solve(root->left, values, ans);
    solve(root->right, values, ans);
    values.pop_back();
  }
 vector<string> binaryTreePaths(TreeNode* root) {
    vector<int>values;
    vector<string>ans;
    solve(root,values,ans);
    return ans;
  }
};

Upvotes: 3

Ajax1234
Ajax1234

Reputation: 71461

You can use recursion with a generator:

def get_paths(d, _c = []):
  val, _l, _r = d
  if _l is None and _r is None:
    yield [*_c, val]
  if _l is not None:
    yield from get_paths(_l, _c = _c+[val])
  if _r is not None:
    yield from get_paths(_r, _c = _c+[val])

print(list(get_paths((1,(2,(4,(7,None,None),None),(5, None, None)),(3,None,(6, None,None))))))

Output:

[[1, 2, 4, 7], [1, 2, 5], [1, 3, 6]]

Upvotes: 0

Related Questions