Sum of alternate leaf nodes in bst

Sum of alternate leaf nodes

Here given code implementation process.

//C Program 
//Sum of alternate leaf nodes in bst
#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 alternate_sum(struct Node*root,int *counter)
{ 
  if(root!=NULL)
  {
    if(root->left==NULL && root->right==NULL)
    { 
      (*counter)++;
      
      if(*counter %2 == 0)
      {
        return root->data;
      }
    }
    return alternate_sum(root->left,counter)+alternate_sum(root->right,counter);
  }
  return 0;
}
void leaf_sum(struct Node*root)
{
  if(root!=NULL)
  {
    int counter=-1;
    printf("\n Alternate leaf node sum : %d",alternate_sum(root,&counter));
    
  }
  else
  {
    printf("\n Empty BST\n");
  }
}
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        19
         / \     /   \
        2   4   8     31
               / \    / \
              7   15 25  50  

  */                

  add(&root,5); 
  add(&root,3); 
  add(&root,19); 
  add(&root,2); 
  add(&root,4); 
  add(&root,8); 
  add(&root,31); 
  add(&root,7); 
  add(&root,25); 
  add(&root,15); 
  add(&root,50); 

  inorder(root);

  leaf_sum(root);
  return 0;
}

Output

  2   3   4   5   7   8  15  19  25  31  50 
 Alternate leaf node sum : 34
//C++ Program 
//Sum of alternate leaf nodes in bst
#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*);
  void leaf_sum();
  int alternate_sum( Node*,int *);

};
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 :: alternate_sum( Node*root,int *counter)
{ 
  if(root!=NULL)
  {
    if(root->left==NULL && root->right==NULL)
    { 
      (*counter)++;
      
      if(*counter % 2 == 0)
      {
        return root->data;
      }
    }
    return alternate_sum(root->left,counter)+alternate_sum(root->right,counter);
  }
  return 0;
}
void BST :: leaf_sum()
{
  if(root!=NULL)
  {
    int counter=-1;
    cout<<"\n Alternate leaf node sum : "<<alternate_sum(root,&counter);
    
  }
  else
  {
    cout<<("\n Empty BST\n");
  }
}
int main()
{

  BST obj;

  //Add nodes in binary search tree
  /*
         5
      /    \ 
     /      \
    3        19
   / \     /   \
  2   4   8     31
         / \    / \
        7   15 25  50  

  */                

  obj.add(5); 
  obj.add(3); 
  obj.add(19); 
  obj.add(2); 
  obj.add(4); 
  obj.add(8); 
  obj.add(31); 
  obj.add(7); 
  obj.add(25); 
  obj.add(15); 
  obj.add(50); 

  obj.inorder(obj.root);

  obj.leaf_sum();

  return 0;
}

Output

 2  3  4  5  7  8  15  19  25  31  50
 Alternate leaf node sum : 34
//Java program
//Sum of alternate leaf nodes in bst
public class BST
{

  static class Node
  {
    int data;
    Node left,right;
  }
  public Node root;
  private int counter;
  //Class constructors
  BST()
  {
    root=null;
    counter=-1;

  } 

  //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 alternate_sum( Node root)
  { 
    if(root!=null)
    {
      if(root.left==null && root.right==null)
      { 
        counter++;

        if(counter % 2 == 0)
        {
          return root.data;
        }
      }
      return alternate_sum(root.left)+alternate_sum(root.right);
    }
    return 0;
  }
  public void leaf_sum()
  {
    if(root!=null)
    {
      counter=-1;
      System.out.println("\n Alternate leaf node sum : "+alternate_sum(root));

    }
    else
    {
      System.out.println("\n Empty BST\n");
    }
  }
  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        19
     / \     /   \
    2   4   8     31
           / \    / \
          7   15 25  50  

    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(19); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(31); 
    obj.add(7); 
    obj.add(25); 
    obj.add(15); 
    obj.add(50); 

    obj.inorder(obj.root);

    obj.leaf_sum();

 }
}

Output

  2  3  4  5  7  8  15  19  25  31  50
 Alternate leaf node sum : 34
#Python Program 
#Sum of alternate leaf nodes in bst
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
    self.counter=-1
  
  #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 alternate_sum(self, root): 
    if(root!=None):

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

        self.counter+=1

        if(self.counter % 2 == 0):

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

    if(self.root!=None):

      self.counter=-1
      print("\n Alternate leaf node sum : ",self.alternate_sum(self.root))

    
    else:

      print("\n Empty BST\n")
    
  
  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        19
   #  / \     /   \
   # 2   4   8     31
   #        / \    / \
   #       7   15 25  50  
                

  obj.add(5) 
  obj.add(3) 
  obj.add(19) 
  obj.add(2) 
  obj.add(4) 
  obj.add(8) 
  obj.add(31) 
  obj.add(7) 
  obj.add(25) 
  obj.add(15) 
  obj.add(50) 

  obj.inorder(obj.root)

  obj.leaf_sum()

if __name__ =="__main__":
  main()

Output

2  3  4  5  7  8  15  19  25  31  50  
 Alternate leaf node sum :  34
//C# program
//Sum of alternate leaf nodes in bst
using System;
public class Node
{
  public int data;
  public Node left,right;
}
public class BST
{


  public Node root;
  private int counter;
  //Class constructors
  BST()
  {
    root=null;
    counter=-1;

  } 

  //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 alternate_sum( Node root)
  { 
    if(root!=null)
    {
      if(root.left==null && root.right==null)
      { 
        counter++;

        if(counter % 2 == 0)
        {
          return root.data;
        }
      }
      return alternate_sum(root.left)+alternate_sum(root.right);
    }
    return 0;
  }
  public void leaf_sum()
  {
    if(root!=null)
    {
      counter=-1;
      Console.WriteLine("\n Alternate leaf node sum : "+alternate_sum(root));

    }
    else
    {
      Console.WriteLine("\n Empty BST\n");
    }
  }
  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        19
     / \     /   \
    2   4   8     31
           / \    / \
          7   15 25  50  

    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(19); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(31); 
    obj.add(7); 
    obj.add(25); 
    obj.add(15); 
    obj.add(50); 

    obj.inorder(obj.root);

    obj.leaf_sum();

  }
}

Output

  2  3  4  5  7  8  15  19  25  31  50
 Alternate leaf node sum : 34
<?php
//Php program 
//Sum of alternate leaf nodes in bst
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 alternate_sum( $root,&$counter)
  { 
    if($root!=NULL)
    {
      if($root->left==NULL && $root->right==NULL)
      { 
        $counter++;

        if($counter % 2 == 0)
        {
          return $root->data;
        }
      }
      return $this->alternate_sum($root->left,$counter)+$this->alternate_sum($root->right,$counter);
    }
    return 0;
  }
  function leaf_sum()
  {
    if($this->root!=NULL)
    {
      $counter=-1;
      echo "\n Alternate leaf node sum : ".$this->alternate_sum($this->root,$counter);

    }
    else
    {
      echo ("\n Empty BST\n");
    }
  }
  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        19
   / \     /   \
  2   4   8     31
         / \    / \
        7   15 25  50  

  */                

  $obj->add(5); 
  $obj->add(3); 
  $obj->add(19); 
  $obj->add(2); 
  $obj->add(4); 
  $obj->add(8); 
  $obj->add(31); 
  $obj->add(7); 
  $obj->add(25); 
  $obj->add(15); 
  $obj->add(50); 

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

  $obj->leaf_sum();
}
main();
?>

Output

  2  3  4  5  7  8  15  19  25  31  50
 Alternate leaf node sum : 34
# Ruby Program
# Sum of alternate leaf nodes in bst

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, :counter
  attr_accessor :root, :counter
  def initialize() 
    @root = nil
    @counter = 0
  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 alternate_sum(head) 
    if (head != nil) 
      if (head.left == nil and head.right == nil) 
        @counter += 1
        if (@counter % 2 == 0) 
          return head.data
        end
      end
      return (self.alternate_sum(head.left) + self.alternate_sum(head.right))
    end
    return 0
  end
  def leaf_sum() 
    if (@root != nil) 
      @counter = -1
      print("\n Alternate leaf node sum  :", self.alternate_sum(@root))
    else 
      print("\n Empty BST\n")
    end
  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        19
  #  / \     /   \
  # 2   4   8     31
  #        / \    / \
  #       7   15 25  50 
  # 
  obj.add(5)
  obj.add(3)
  obj.add(19)
  obj.add(2)
  obj.add(4)
  obj.add(8)
  obj.add(31)
  obj.add(7)
  obj.add(25)
  obj.add(15)
  obj.add(50)
  obj.inorder(obj.root)
  obj.leaf_sum()
end


main()

Output

  2  3  4  5  7  8  15  19  25  31  50
 Alternate leaf node sum  :34
/*
 Node Js Program
 Sum of alternate leaf nodes in bst
*/

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

  constructor() {
    this.root = null;
    this.counter = 0;
  }
  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");
    }
  }
  alternate_sum(head) {
    if (head != null) {
      if (head.left == null && head.right == null) {
        this.counter++;
        if (this.counter % 2 == 0) {
          return head.data;
        }
      }
      return this.alternate_sum(head.left) + this.alternate_sum(head.right);
    }
    return 0;
  }
  leaf_sum() {
    if (this.root != null) {
      this.counter = -1;
      process.stdout.write("\n Alternate leaf node sum : " + this.alternate_sum(this.root));
    } else {
      process.stdout.write("\n Empty BST\n");
    }
  }
  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        19
     / \     /   \
    2   4   8     31
           / \    / \
          7   15 25  50  

    */        
  obj.add(5);
  obj.add(3);
  obj.add(19);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(31);
  obj.add(7);
  obj.add(25);
  obj.add(15);
  obj.add(50);
  obj.inorder(obj.root);
  obj.leaf_sum();
}

main();

Output

  2  3  4  5  7  8  15  19  25  31  50
 Alternate leaf node sum  :34
/*
 Swift 4 Program
 Sum of alternate leaf nodes in bst
*/

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? ;
  var counter: Int;
  init() {
    self.root = nil;
    self.counter = 0;
  }
  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 alternate_sum(_ head: Node? )->Int {
    if (head != nil) {
      if (head!.left == nil && head!.right == nil) {
        self.counter += 1;
        if (self.counter % 2 == 0) {
          return head!.data;
        }
      }
      return self.alternate_sum(head!.left) + self.alternate_sum(head!.right);
    }
    return 0;
  }
  func leaf_sum() {
    if (self.root != nil) {
      self.counter = -1;
      print("\n Alternate leaf node sum : ", self.alternate_sum(self.root));
    } else {
      print("\n Empty BST\n");
    }
  }
  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        19
     / \     /   \
    2   4   8     31
           / \    / \
          7   15 25  50  

  */        
  obj.add(5);
  obj.add(3);
  obj.add(19);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(31);
  obj.add(7);
  obj.add(25);
  obj.add(15);
  obj.add(50);
  obj.inorder(obj.root);
  obj.leaf_sum();
}
main();

Output

  2  3  4  5  7  8  15  19  25  31  50
 Alternate leaf node sum  :34


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