finding all numbers which a tree can generates by add or multiply nodes

Question

I want to find a path from the root of a binary search tree, whether it can generate a specific number by adding or multiplying nodes.

In another word, I want to show all numbers, which can generate by adding * or + between nodes of a path.

Note that the path should starts from the root to a leaf.

For example:

tree nodes: 10, 8, 3

number can produce from this path:

240 => 10 * 8 * 3

110 => 10 * (8 + 3)

21 => 10 + 8 + 3

83 => (10 * 8) + 3

54 => (10 + 8) * 3

34 => 10 + (8 * 3)

I wrote this code, which doesn't include parentheses.

 private void findThePath(TreeNode tnode, int result, int n, List paths) {
        // if node is null, return
        if (tnode == null)
            return;

    //adding nodes to this list, in order to save the path
    paths.add(tnode);

    // if node is leaf node, and its data equals
    // to user input, its path highlighted
    if (tnode.leftCircle == null && tnode.rightCircle == null) {
        if (result == n) {
            paths.forEach(t -> t.highlightFlag = true);
            paths.forEach(t -> System.out.print(t.rootCircle.getSearchKey() + " "));
        }
    }

    // if left child exists, check for leaf,
    // and insert * or + sign between nodes,
    // recursively
    if (tnode.leftCircle != null) {
        findThePath(tnode.leftCircle, result + tnode.leftCircle.rootCircle.getSearchKey(), n, paths);
        findThePath(tnode.leftCircle, result * tnode.leftCircle.rootCircle.getSearchKey(), n, paths);
    }

    // if right child exists, check for leaf
    // and insert * or + sign between nodes,
    // recursively
    if (tnode.rightCircle != null) {
        findThePath(tnode.rightCircle, result + tnode.rightCircle.rootCircle.getSearchKey(), n, paths);
        findThePath(tnode.rightCircle, result * tnode.rightCircle.rootCircle.getSearchKey(), n, paths);
    }

    //we need to remove the last node in list because
    //its not in left or right of the nodes
    paths.remove(paths.size() - 1);
}

see the output here:

which it doesn't contain 8 * (5 + 3) and 8 + (5 * 3).

Specify which child is *, which child is + and if it is a binary tree or n-ary tree? and more importantly the effort that you made. — SomeDude
Those also "/" and "-" are allowed? I guess you should find first all paths and then check all possible number that can be created... — dWinder

anand anand · Accepted Answer · 2018-12-31T10:02:46

If the number generated is for three nodes, then traverse recursively the tree and at every node check if it has both left and right nodes for which the given equations can be run and if it gives number, print the nodes.

finding all numbers which a tree can generates by add or multiply nodes

1 Answers