**Question :**

WAP to find the Size of a binary tree in O(n) time complexity.

**Solution :**

The problem is solved in recurssive way.

**Algorithm :**

** Step 1 :** If tree is empty then return 0.

** Step 2 :** Recursively traverse left sub-tree and right sub-tree.

** Step 3 :** For each node of left sub-tree add 1 and for each node of right sub-tree add 1 to the result and return the same.

**Program :**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
package com.ai1tutorial.dsalgo.binarytree; class BinaryTree { int data; BinaryTree left; BinaryTree right; public BinaryTree(int data) { super(); this.data = data; this.left = null; this.right = null; } } public class SizofBinaryTree { public static void main(String[] args){ BinaryTree root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.left.left.right = newNode(9); System.out.println("Size of Binary Tree = "+sizeofBinaryTree(root)); } private static BinaryTree newNode(int data) { BinaryTree node = new BinaryTree(data); node.left = node.right = null; return node; } private static int sizeofBinaryTree(BinaryTree root) { if(null == root){ return 0; } return 1+sizeofBinaryTree(root.left)+sizeofBinaryTree(root.right); } } |

1 2 3 4 |
OutPut: Size of Binary Tree = 9 |