Sum of all leaf nodes of binary search tree

Sum of leaf nodes

Here given code implementation process.

//C Program 
//Sum of all leaf nodes of binary search tree
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;
      //Iterate binary tree and add new node to proper position
      while(find != NULL)
      {
        if(find -> data > data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}

int leaf_sum(struct Node*root)
{
  if(root!=NULL)
  {
    if(root->left==NULL && root->right==NULL)
    {
      return root->data;
    }
    return leaf_sum(root->left)+leaf_sum(root->right);
  }
  return 0;
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {

    inorder(root->left);
    printf("%3d ",root->data );
    inorder(root->right);
  }
}
int main(){

  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
              5
            /   \ 
           /     \
          3       9
         / \     /  \
        2   4   8    10
               / 
              6

  */                

  add(&root,5); 
  add(&root,3); 
  add(&root,9); 
  add(&root,2); 
  add(&root,4); 
  add(&root,8); 
  add(&root,10); 
  add(&root,6); 
  

  inorder(root);

  printf("\n Leaf node sum : %d \n",leaf_sum(root));
  return 0;
}

Output

  2   3   4   5   6   8   9  10 
 Leaf node sum : 22 
//C++ Program 
//Sum of all leaf nodes of binary search tree
#include <iostream>
using namespace std;
//structure of Binary Search Tree node
struct Node

{
  int data;
  struct Node *left,*right; 
};
class BST
{

public:
  Node*root;
  BST();
  //public methods
  void add(int);
  void inorder(Node*);
  int leaf_sum(Node*);
  
};
BST::BST()
{
  root=NULL;
}
//Adding a new node in binary search tree
void BST :: add(int data)
{
  //Create a dynamic node of binary search tree 
   Node *new_node = new Node();

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(root == NULL)
    {
      //When adds a first node in binary tree
      root = new_node;
    }
    else
    {
       Node *find = root;

      //add new node to proper position
      while(find != NULL)
      {
        if(find -> data >= data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { 
            //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }
  else
  {
    cout<<("Memory Overflow\n");
  }
}
void BST :: inorder(Node*root)
{
  if(root!=NULL)
  {

    inorder(root->left);
    cout<<"  "<< root->data;
    inorder(root->right);
  }
}
int BST :: leaf_sum( Node*root)
{ 
  if(root!=NULL)
  {
    if(root->left==NULL && root->right==NULL)
    { 
     
      return root->data;
      
    }
    return leaf_sum(root->left)+leaf_sum(root->right);
  }
  return 0;
}
int main()
{

  BST obj;

  //Add nodes in binary search tree
  /*
        5
      /   \ 
     /     \
    3       9
   / \     /  \
  2   4   8    10
         / 
        6

  */                

  obj.add(5); 
  obj.add(3); 
  obj.add(9); 
  obj.add(2); 
  obj.add(4); 
  obj.add(8); 
  obj.add(10); 
  obj.add(6); 
  

  obj.inorder(obj.root);

  cout<<"\n Leaf node sum :  "<<obj.leaf_sum(obj.root)<<endl;

  return 0;
}

Output

  2  3  4  5  6  8  9  10
 Leaf node sum :  22
//Java program
//Sum of all leaf nodes of binary search tree
public class BST
{

  static class Node
  {
    int data;
    Node left,right;
  }
  public Node root;

  //Class constructors
  BST()
  {
    root=null;
  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = null;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      System.out.println("Memory Overflow");
    }
  }

  public int leaf_sum(Node root)
  {
   if(root!=null)
    {
      if(root.left==null && root.right==null)
      { 
       
        return root.data;
        
      }
      return leaf_sum(root.left)+leaf_sum(root.right);
    }
    return 0;
  }
  public void inorder(Node root)
  {
    if(root!=null)
    {

      inorder(root.left);
      System.out.print("  "+ root.data);
      inorder(root.right);
    }
  }
  public static void main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /* 
                5
              /   \ 
             /     \
            3       9
           / \     /  \
          2   4   8    10
                 / 
                6
    
    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(10); 
    obj.add(6); 
    

    obj.inorder(obj.root);

    System.out.println("\n Leaf node sum :  "+obj.leaf_sum(obj.root));
 }
}

Output

  2  3  4  5  6  8  9  10
 Leaf node sum :  22
#Python Program 
#Sum of all leaf nodes of binary search tree
class Node:
  def __init__(self,data):
    self.data=data
    self.left=None
    self.right=None

   
class BST:

  def __init__(self):

   # Assign default value
    self.root=None

  
  #insert  element
  def add(self,data):

    # Create a dynamic node of binary search tree 
    new_node = Node(data)

    if(self.root == None):
      # When adds a first node in binary tree
      self.root = new_node
    
    else:
      find = self.root

      # add new node to proper position
      while(find != None):

        if(find.data >= data): 

          if(find.left==None):

            find.left = new_node
            break
          
          else: 

            # visit left sub-tree
            find = find.left
          
        
        else:

          if(find.right == None):

            find.right = new_node
            break
          
          else:

            # visit right sub-tree
            find = find.right

  def leaf_sum(self, root): 

    if(root!=None):

      if(root.left==None  and  root.right==None): 

        return root.data
        
      
      return self.leaf_sum(root.left) + self.leaf_sum(root.right)
    
    return 0
  

  def inorder(self, root):
    if(root!=None):

      self.inorder(root.left)
      print(root.data, end="  ")
      self.inorder(root.right)
    
  

def main():

  obj = BST()


  #Add nodes in binary search tree
  # 
  #            5
  #          /   \ 
  #         /     \
  #        3       9
  #       / \     /  \
  #      2   4   8    10
  #             / 
  #            6
  #
  #                

  obj.add(5) 
  obj.add(3) 
  obj.add(9) 
  obj.add(2) 
  obj.add(4) 
  obj.add(8) 
  obj.add(10) 
  obj.add(6) 
  

  obj.inorder(obj.root)

  print("\n Leaf node sum :  ",obj.leaf_sum(obj.root))

if __name__ =="__main__":
  main()

Output

2  3  4  5  6  8  9  10  
 Leaf node sum :   22
//C# program
//Sum of all leaf nodes of binary search tree
using System;
public class Node
{
  public int data;
  public Node left,right;
}

public class BST
{


  public Node root;

  //Class constructors
  BST()
  {
    root=null;
  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = null;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      Console.WriteLine("Memory Overflow");
    }
  }

  public int leaf_sum(Node root)
  {
    if(root!=null)
    {
      if(root.left==null && root.right==null)
      { 

        return root.data;

      }
      return leaf_sum(root.left)+leaf_sum(root.right);
    }
    return 0;
  }
  public void inorder(Node root)
  {
    if(root!=null)
    {

      inorder(root.left);
      Console.Write("  "+ root.data);
      inorder(root.right);
    }
  }
  public static void Main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /* 
                5
              /   \ 
             /     \
            3       9
           / \     /  \
          2   4   8    10
                 / 
                6
    
    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(10); 
    obj.add(6); 


    obj.inorder(obj.root);

    Console.WriteLine("\n Leaf node sum :  "+obj.leaf_sum(obj.root));
  }
}

Output

  2  3  4  5  6  8  9  10
 Leaf node sum :  22
<?php
//Php program 
//Sum of all leaf nodes of binary search tree
class Node
{
  public $data;
  public $left;
  public $right;
  function __construct($data)
  {
    $this->data = $data;
    $this->length = NULL;
    $this->right = NULL;
  }
}
class BST
{

  public $root;
  function __construct()
  {
    $root=NULL;
  }

 //Adding a new node in binary search tree
  function add($data)
  {
    //Create a dynamic node of binary search tree 
    $new_node = new Node($data);

    if($this->root == NULL)
    {
      //When adds a first node in binary tree
      $this->root = $new_node;
    }
    else
    {
      $find = $this->root;

      //add new node to proper position
      while($find != NULL)
      {
        if($find->data >= $data)
        { 
          if($find->left==NULL)
          {
            $find->left = $new_node;
            break;
          }
          else
          { 
          //visit left sub-tree
            $find = $find->left;
          }
        }
        else
        {
          if($find->right == NULL)
          {
            $find->right = $new_node;
            break;
          }
          else
          {
          //visit right sub-tree
            $find = $find->right;
          }
        }
      }
    }

  }

  function leaf_sum( $root)
  { 
    if($root!=NULL)
    {
      if($root->left==NULL && $root->right==NULL)
      { 
        
        return $root->data;
      }
      return $this->leaf_sum($root->left)+$this->leaf_sum($root->right);
    }
    return 0;
  }
  function inorder($root)
  {
    if($root!=NULL)
    {

      $this->inorder($root->left);
      echo "  ". $root->data;
      $this->inorder($root->right);
    }
  }
}
function main()
{
  //Make a object of BST class
  $obj= new BST();

  //Add nodes in binary search tree
  /*
          5
        /   \ 
       /     \
      3       9
     / \     /  \
    2   4   8    10
           / 
          6
  
  */                

  $obj->add(5); 
  $obj->add(3); 
  $obj->add(9); 
  $obj->add(2); 
  $obj->add(4); 
  $obj->add(8); 
  $obj->add(10); 
  $obj->add(6); 
  

  $obj->inorder($obj->root);

  echo "\n Leaf node sum :  ".$obj->leaf_sum($obj->root);
}
main();
?>

Output

  2  3  4  5  6  8  9  10
 Leaf node sum :  22
# Ruby Program
# Sum of all leaf nodes of binary search tree

class Node 
  attr_reader :data, :left, :right
  attr_accessor :data, :left, :right
  def initialize(value) 
    @data = value
    @left = nil
    @right = nil
  end
end

class BinarySearchTree 
  attr_reader :root
  attr_accessor :root
  def initialize() 
    @root = nil
  end
  def add(value) 
    new_node = Node.new(value)
    if (new_node != nil) 
      if (@root == nil) 
        @root = new_node
      else 
        find = @root
        while (find != nil) 
          if (find.data >= value) 
            if (find.left == nil) 
              find.left = new_node
              break
            else 
              find = find.left
            end
          else 
            if (find.right == nil) 
              find.right = new_node
              break
            else 
              find = find.right
            end
          end
        end
      end
    else 
      print("\nMemory Overflow\n")
    end
  end
  def leaf_sum(head) 
    if (head != nil) 
      if (head.left == nil and head.right == nil) 
        return head.data
      end
      return self.leaf_sum(head.left) + self.leaf_sum(head.right)
    end
    return 0
  end
  def inorder(head) 
    if (head != nil) 
      self.inorder(head.left)
      print("  ", head.data)
      self.inorder(head.right)
    end
  end
end
def main() 
  obj = BinarySearchTree.new()
  # Add nodes in binary search tree
  # 
  #            5
  #          /   \ 
  #         /     \
  #        3       9
  #       / \     /  \
  #      2   4   8    10
  #             / 
  #            6
  #
  #                

  obj.add(5)
  obj.add(3)
  obj.add(9)
  obj.add(2)
  obj.add(4)
  obj.add(8)
  obj.add(10)
  obj.add(6)
  obj.inorder(obj.root)
  print("\n Leaf node sum  : ", obj.leaf_sum(obj.root) ,"\n")
end


main()

Output

   2   3   4   5   6   8   9   10
 Leaf node sum :   22
/*
 Node Js Program
 Sum of all leaf nodes of binary search tree
*/

class Node {

  constructor(value) {
    this.data = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {

  constructor() {
    this.root = null;
  }
  add(value) {
    var new_node = new Node(value);
    if (new_node != null) {
      if (this.root == null) {
        this.root = new_node;
      } else {
        var find = this.root;
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;
              break;
            } else {
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;
              break;
            } else {
              find = find.right;
            }
          }
        }
      }
    } else {
      process.stdout.write("\nMemory Overflow\n");
    }
  }
  leaf_sum(head) {
    if (head != null) {
      if (head.left == null && head.right == null) {
        return head.data;
      }
      return this.leaf_sum(head.left) + this.leaf_sum(head.right);
    }
    return 0;
  }
  inorder(head) {
    if (head != null) {
      this.inorder(head.left);
      process.stdout.write("  " + head.data);
      this.inorder(head.right);
    }
  }
}

function main() {
  var obj = new BinarySearchTree();
  //Add nodes in binary search tree
  /* 
            5
          /   \ 
         /     \
        3       9
       / \     /  \
      2   4   8    10
             / 
            6

  */ 
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(10);
  obj.add(6);
  obj.inorder(obj.root);
  process.stdout.write("\n Leaf node sum :  " + obj.leaf_sum(obj.root) + "\n");
}

main();

Output

   2   3   4   5   6   8   9   10
 Leaf node sum :   22
/*
 Swift 4 Program
 Sum of all leaf nodes of binary search tree
*/

class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func add(_ value: Int) {
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              break;
            } else {
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              break;
            } else {
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("\nMemory Overflow\n");
    }
  }
  func leaf_sum(_ head: Node? ) -> Int {
    if (head != nil) {
      if (head!.left == nil && head!.right == nil) {
        return head!.data;
      }
      return self.leaf_sum(head!.left) + self.leaf_sum(head!.right);
    }
    return 0;
  }
  func inorder(_ head: Node? ) {
    if (head != nil) {
      self.inorder(head!.left);
      print("  ", head!.data,terminator:"");
      self.inorder(head!.right);
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  //Add nodes in binary search tree
  /* 
              5
            /   \ 
           /     \
          3       9
         / \     /  \
        2   4   8    10
               / 
              6
  
  */     
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(10);
  obj.add(6);
  obj.inorder(obj.root);
  print("\n Leaf node sum :  ", obj.leaf_sum(obj.root) );
}
main();

Output

   2   3   4   5   6   8   9   10
 Leaf node sum :   22


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved