This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/count-number-of-leaf-nodes-in-binary-tree/.
Problem
Count leaf nodes in a binary treeSolution
Method 1 - RecursiveHere is the logic:
- If node is NULL then return 0.
- Else If left and right child nodes are NULL return 1.
- Else recursively calculate leaf count of the tree using below formula.
Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree
Here is the recursive solution:
int countLeaves(Node node){ if( node == null ) return 0; if( node.left == null && node.right == null ) { return 1; } else { return countLeaves(node.left) + countLeaves(node.right); } }
Time complexity - O(n)
Method 2 - Iterative
Here we can use Queue. Idea is to use Level Order traversal.
int countLeaves(Node root) { int count=0; if(root==null) return 0; Queue<Node> myqueue = new Queue<Node>(); myqueue.push(root); while(!myqueue.empty()) { Node temp; temp=myqueue.pop();//take the top element from the queue if(temp.left==null && temp.right==null) count++; if(temp.left!=null) myqueue.push(temp.left); if(temp.right!=null) myqueue.push(temp.right); } return count; }
Time complexity - O(n)
Space Complexity - O(n) for queue
Referenes
0 comments:
Post a Comment