Count nodes in each subtree

0
votes

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:

enter image description here

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

3
recursiontree
The fact that the count of nodes in a tree is exactly the sum of the count of nodes in the left and right sub-trees plus one for the root node should lend itself pretty readily to a simple recursive method. Transforming that recursive method to an iterative method to avoid stack overflow on huge trees is left as an exercise to the reader, if it's necessary to handle such trees... - twalberg

3 Answers

1
votes

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...

1
votes

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;
}
0
votes

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.