Count nodes in each subtree

Question

I need to solve a bigger algorithm and one of the steps is count nodes in each subtree I dont need the code to do it but I need help to understand

The exercise is like this:

basically i need to return a new tree , each node containing the value of the node , and the number of elements in the left subtree and number of elements in the right subtree.

this is the method

public AB NumberOnEachSubtree(NodeAB a,NodeAB b) {

}

i think i can make the subtree in the first line of code and then add each node as I go trough the orignal tree, when you come back in recursion count number of nodes

but I dont have idea how to do it.. help

each node has left node and right node and numberNodesLeft and numberNodesRight

Answer 1

Here is a solution in JAVA. Basically, create a TreeNode class that includes number of left Nodes and number of right Nodes. I realize this answer is probably too late for OP but hope it will help someone in the long run.

class TreeNode{
    TreeNode left;
    TreeNode right;
    int leftNodes;
    int rightNodes;
    int value;
    public TreeNode(int value){
        value=value;
        TreeNode left = null;
        TreeNode right = null;
        leftNodes =rightNodes=0;
    }
}

public void numofRightLeftSubTree(TreeNode root){
    numNodes(root);
    System.out.println("number of left tree nodes are " + root.leftNodes );
    System.out.println("number of right tree nodes are " + root.rightNodes);

}

public int numNodes(TreeNode root) {
    if (root == null) return 0;
    int left = numNodes(root.left);
    int right = numNodes(root.right);

    root.leftNodes = left;
    root.rightNodes = right;

    return left + right + 1;
}

Answer 2

Here is a solution in Haskell, since it is so concise you should be able to figure out the algorithm's steps, even if not familiar with the language.

A suitable tree data type:

data Tree a = Nil
  | Leaf a
  | Br a (Tree a) (Tree a) deriving Show

Your example tree from the picture:

t = Br 3 (Br 5 Nil (Leaf 9))
          (Br 8 (Leaf 1) Nil)

The recursive function, transforming a tree with Integer nodes into a tree with triples of Integers as nodes. The recursive solutions are in tl and tr for the left and right subtree, and the count function counts the nodes of a transformed (sub)tree.

transform :: Tree Integer -> Tree (Integer, Integer, Integer)
transform Nil = Nil
transform (Leaf a) = Leaf (0, a, 0)
transform (Br a l r) = (Br (count tl, a, count tr) tl tr)
  where tl = transform l 
        tr = transform r 

        count Nil      = 0
        count (Leaf a) = 1
        count (Br a l r) = count l + count r + 1

If you save the above code in a .hs file and try it in a Haskell interpreter, you can play with it. In the interpreter hugs:

Main> t
Br 3 (Br 5 Nil (Leaf 9)) (Br 8 (Leaf 1) Nil)
Main> transform t
Br (2,3,2) (Br (0,5,1) Nil (Leaf (0,9,0))) (Br (1,8,0) (Leaf (0,1,0)) Nil)

I hope this helps you developing the right solution in your language of choice.

Answer 3

I can give you a pseudocode of the algorithm:

class TreeNode
{
    integer CountLeftChildren()
    {
        integer count = 0
        if (hasLeftChildren)
        {
             foreach(child in LeftChildren)
             {
                  count++
                  child+=child.CountLeftChildren()
                  child+=child.CountRightChildren()
             }
        }
        return count
    }

    integer CountRightChildren()
    {
        integer count = 0
        if (hasRightChildren)
        {
             foreach(child in RightChildren)
             {
                  count++
                  child+=child.CountLeftChildren()
                  child+=child.CountRightChildren()
             }
        }
        return count
    }
}

Hope it helps...