CODEWITHSUNDEEP
data-structurestreebinary-tree
Sachit Murarka
Sachit Murarka

Reputation: 183

Count no of child nodes for every node

Given a tree:

      F
    /   \
   C     E
  / \   /
 A   B D

I want to count no of child nodes for every nodes. What will be optimized algorithm?

Upvotes: 1

Views: 1217

Answers (1)

Stefan Haustein
Stefan Haustein

Reputation: 18793

If the child count is supposed to include grandchildren, do a postorder traversal, recursively counting branch sizes in O(n):

int countChildren(Node node) {
  int leftCount = node.left == null ? 0 : (countChildren(root.left) + 1);
  int rightCount = node.right == null ? 0 : (countChildren(root.right) + 1);

  int totalChildren = leftCount + rightCount;

  System.out.println(node.name + ":" + totalChildren);

  return totalChildren;
}

Upvotes: 1

Related Questions