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, 

No comments:
Write comments