Topic: Tree
1) Size of Binary Tree | Easy |
2) Minimum element in BST | Easy |
3) Sum of Binary Tree | Easy |
4) Count leaves in a binary tree | Easy |
5) Count Non-leaf nodes in a binary tree | Easy |
6) Maximum Depth Of Binary Tree | Easy |
Size of Binary Tree
Input :
Testcase 2: Given Tree is :
10
/ \
5 9
\ / \
1 3 6
There are six nodes in the tree .
public static int getSize(Node root)
{
// Approach
/*
1. Level order traversal will be used
2. we will not push N to stack
3. while loop will run until stack is empty
*/
Stack<Node> st = new Stack<>();
st.push(root);
int count = 1;
while(!st.isEmpty())
{
Node p = st.pop();
if(p.right!=null){
st.push(p.right);
count++;
}
if(p.left!=null){
st.push(p.left);
count++;
}
}
return count;
}
Minimum element in BST
Input:
5
/ \
4 6
/ \
3 7
/
1
Output: 1
int minValue(Node node) {
// till node.left is not equal to null
// store max in variable
// compare nodes left to max in one while loop
if(node==null) return -1;
int minn = node.data;
while(node.left!=null){
if(node.left.data<minn){
minn=node.left.data;
}
node = node.left;
}
return minn;
}
Sum of Binary Tree
Input:
2
2
1 2 L 1 -1 N
6
1 2 L 1 3 R 2 -1 N 2 -1 N 3 3 L 3 -1 N
Output:
3
9
static int sumBT(Node head){
Stack<Node> st = new Stack<>();
int sum = 0;
st.push(head);
sum = sum + head.data;
while(!st.isEmpty()){
Node p = st.pop();
if(p.right!=null){
sum = sum + p.right.data;
st.push(p.right);
}
if(p.left!=null){
sum = sum + p.left.data;
st.push(p.left);
}
}
return sum;
}
Count leaves in a binary tree
Input:
Given Tree is
4
/ \
8 10
/ / \
7 5 1
/
3
Output:
3
Explanation:
Three leaves are 3 , 5 and 1.
int countLeaves(Node node)
{
// level order traversal used to reach all the nodes
// stack is used to store the address of last visited node
// if both left and right child of popped element is not present the do count++
Stack<Node> st = new Stack<>();
int count = 0;
st.push(node);
while(!st.isEmpty()){
Node popped = st.pop();
if(popped.right!=null){
st.push(popped.right);
}
if(popped.left!=null){
st.push(popped.left);
}
if(popped.left==null && popped.right==null){
count++;
}
}
return count;
}
Count Non-leaf nodes in a binary tree
int countNonLeafNodes(Node node) {
Stack<Node> st = new Stack<>();
int count = 0;
int inc = 0;
st.push(node);
while(!st.isEmpty()){
Node popped = st.pop();
if(popped.right!=null){
st.push(popped.right);
inc++;
}
if(popped.left!=null){
st.push(popped.left);
inc++;
}
if(popped.left==null && popped.right==null){
count++;
}
}
return inc-count+1; // 1 is for root node
}
Maximum Depth Of Binary Tree
Input:
root --> 1
/ \
3 2
/
4
Output: 3
Explanation:
Maximum depth is between nodes 1 and 4, which is 3.
public static int maxDepth(Node root) {
// Approach 1 - Level order Traversal
// Approach 2 - Find height of tree using recursion
// Implementing approach 2
if(root==null){
return 0;
}
else{
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
Thank you for reading :)