Finding the cheapest path down a binary tree?

Question

I'm struggling to find an algorithm for the following problem:

Given a binary tree of integers, the cost of a branch (a.k.a. a branch that starts from the root and reaches the leaf node) is given by the sum of his values. Write a function that returns a list of the cheapest branch.

Can anyone recommend me the easiest way to complete this exercise?

Answer 1

It can easily be done recursively . The function prints all the root to leaf paths along with the cheapest branch. I have used ArrayList to add all the nodes from root to leaf. Whenever a leaf node is reached i just check if the maxSum so far is smaller than then the current root to leaf path and update it.

class Node {

    public int info;
    public Node left;
    public Node right;

    public Node(int info) {
        this(info, null, null);
    }

    public Node(int info, Node left, Node right) {
        this.info = info;
        this.left = left;
        this.right = right;
    }

}

public class RootToLeaf {

    private static int maxSum = Integer.MAX_VALUE;
    private static ArrayList<Integer> finalList = new ArrayList<>();

    public static void main(String[] args) {

        Node root = new Node(8);
        root.left = new Node(4);
        root.left.left = new Node(3);
        root.left.right = new Node(1);
        root.right = new Node(5);
        root.right.right = new Node(11);
        ArrayList<Integer> list = new ArrayList<Integer>();
        path(root, list,0);
        System.out.println("Cheapest list is - " + finalList.toString() +  " and minimum sum is " + maxSum);

    }

    private static void path(Node root, ArrayList<Integer> list,int s) {

        if(root==null) {
            return;
        } else {
            list.add(root.info);
            s = s+root.info;
        }

        if ((root.left == null && root.right == null)) {
            System.out.println(list);
            if(maxSum>s) {
                maxSum = s;
                finalList = new ArrayList<>(list);
            }
            return;
        }

        path(root.left, new ArrayList<Integer>(list),s);
        path(root.right, new ArrayList<Integer>(list),s);

    }

}

The out put is as follows :

[8, 4, 3]
[8, 4, 1]
[8, 5, 11]
Cheapest list is - [8, 4, 1] and minimum sum is 13

Answer 2

I would suggest traversing the tree depth first.

You will need three variables:

1) the current cost, wich represents the sum of the values from the root node to the current node.

2) the cheapest path from root to any leaf so far (init it empty)

3) the cheapest cost which represent the cost of the cheapest path

If you reach a node, add its node cost to the current cost (1).

If you reach a leaf, add its node cost as well to the current cost. Then check, if its cost is cheaper than the cheapest cost (3). If it is (or no cheapest cost exists because its the first leaf you reach) set cheapest cost = current cost. and set the cheapest path to the current path (you can store it in a variable itself or just traverse backwards from the current leave to the root node) Then go one node up and check if there is a branch you have not yet visited. If there is, go check it. If not, go another node up and check (and so on...)

Shortcut: When you reach a node and the current cost to it is larger than the cheapest cost, you can skip the whole subtree of that node.

Answer 3

You needed to build priority_queue (c++ stl has this container) of pairs:

• node index
• cost

Priority is cost, ascending.

Algorithm:

Put into the priority_queue pair(root, cost_of_root). Thereafter, loop:

1. Extract pair (node, cost) from the priority_queue
2. If this node is leaf - return pair as best leaf/cost.
3. Else - put to to the priority_queue two pairs: (left_son, cost + left_son.cost), (right_son, cost + right_son.cost).

That's all.

Answer 4

Since a tree is just a specialized graph, Dijkstra's algorithm works great here:

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
2. Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.
4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

Just keep track of which branch has the lowest cost at the end. Return a list with that branch.

Answer 5

As a hint, work from the leaves of the tree upward. The cost of a leaf is just the value inside the leaf. Otherwise, the cost of a the best path starting at a node is given by the cost of that node plus the cost of the cheapest path taken from there. Can you implement this recursively?

Hope this helps!