Showing posts with label Binary Tree Lead node. Show all posts
Showing posts with label Binary Tree Lead node. Show all posts

## Know How to find all leaf nodes in binary tree

Create a Binary Tree with from the given array of values and then find all the leaf nodes from left to right. Leaf nodes are nothing but bottom/last nodes with both left and right subtree's are null.
For the below given Binary tree the list of leaf nodes will be 1, 6, 9

Lets see simple java code to create a binary with the given array of integers and to find the leaf nodes.

```public class BinaryTreeLeafNode {

public static void main(String[] args) {

int val[] = new int[] { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };

BinaryTree obj = new BinaryTree();

BST root = obj.createBinaryTree(val);

obj.getAllLeafNodes(root);
}

public BST createBinaryTree(int[] val) {
BST root = new BST(val[0]); // Initialize root with 1ft element
BST tmpRoot = root; // Temporary root node

for (int i = 1; i < val.length; i++) {

BST lastNode = getLastNode(tmpRoot, val[i]);
if (val[i] > lastNode.data) {
BST tmp = new BST(val[i]);
lastNode.right = tmp;
} else {
BST tmp = new BST(val[i]);
lastNode.left = tmp;
}
}
return root;
}

public void getAllLeafNodes(BST root) {
if (root.left != null) {
getAllLeafNodes(root.left);
}
if (root.right != null) {
getAllLeafNodes(root.right);
}
/*
* If both left and right are null then its leaf node
*/
if(root.left == null && root.right == null) {
System.out.print(root.data + ", ");
}
}

public BST getLastNode(BST root, int val) {

if (val > root.data) {
if (root.right == null) {
return root;
} else
return getLastNode(root.right, val);
} else {
if (root.left == null) {
return root;
} else
return getLastNode(root.left, val);
}
}
}
```

OUTPUT:

```1, 6, 9,
```