Skip to main content

Find right leaf node in a binary search tree

Here given code implementation process.

//C Program 
//Find right leaf node in a 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 add a first node in BST
      *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
  }
}
void right_leaf_nodes(struct Node *root)
{
  if (root != NULL)
  {
    if (root->right != NULL && root->right->left == NULL && root->right->right == NULL)
    {
      //When find right leaf node
      printf("  %d", root->right->data);
    }
    right_leaf_nodes(root->left);
    right_leaf_nodes(root->right);
  }
}
int main()
{
  struct Node *root = NULL;
  //Add nodes in binary search tree
  /*
         17
      /     \
     4       19
    / \     /  \
   3   10  18   20
      /  \        \
     9    16       37
  */
  add( & root, 17);
  add( & root, 4);
  add( & root, 3);
  add( & root, 10);
  add( & root, 19);
  add( & root, 18);
  add( & root, 20);
  add( & root, 37);
  add( & root, 16);
  add( & root, 9);
  right_leaf_nodes(root);
  return 0;
}

Output

  16  37
//Java Program 
//Find right leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
  // Data value 
  public int data;
  // Indicates left and right subtree
  public Node left;
  public Node right;
  public Node(int data)
  {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree
{
  public Node root;
  public BinarySearchTree()
  {
    this.root = null;
  }
  //insert a binary search tree element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(data);
    if (new_node != null)
    {
      if (root == null)
      {
        //When add a first node in BST
        root = new_node;
      }
      else
      {
        Node find = root;
        //Add a new node to its proper position
        while (find != null)
        {
          if (find.data >= data)
          {
            if (find.left == null)
            {
              find.left = new_node;
              return;
            }
            else
            {
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if (find.right == null)
            {
              find.right = new_node;
              return;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      System.out.println("Memory Overflow");
    }
  }
  void right_leaf_nodes(Node root)
  {
    if (root != null)
    {
      if (root.right != null && root.right.right == null && root.right.left == null)
      {
        //When find right leaf node
        System.out.print("  " + root.right.data);
      }
      right_leaf_nodes(root.left);
      right_leaf_nodes(root.right);
    }
  }
  public static void main(String[] args)
  {
    BinarySearchTree obj = new BinarySearchTree();
    //Add nodes in binary search tree
    /*
           17
        /     \
       4       19
      / \     /  \
     3   10  18   20
        /  \        \
       9    16       37
    */
    obj.add(17);
    obj.add(4);
    obj.add(3);
    obj.add(10);
    obj.add(19);
    obj.add(18);
    obj.add(20);
    obj.add(37);
    obj.add(16);
    obj.add(9);
    obj.right_leaf_nodes(obj.root);
  }
}

Output

  16  37
//Include header file
#include <iostream>

using namespace std;
//C++ Program 
//Find right leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
  public:
    // Data value 
    int data;
  // Indicates left and right subtree
  Node * left;
  Node * right;
  Node(int data)
  {
    this->data = data;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree
{
  public: Node * root;
  BinarySearchTree()
  {
    this->root = NULL;
  }
  //insert a binary search tree element
  void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node * new_node = new Node(data);
    if (new_node != NULL)
    {
      if (this->root == NULL)
      {
        //When add a first node in BST
        this->root = new_node;
      }
      else
      {
        Node * find = this->root;
        //Add a new node to its proper position
        while (find != NULL)
        {
          if (find->data >= data)
          {
            if (find->left == NULL)
            {
              find->left = new_node;
              return;
            }
            else
            {
              //visit left sub-tree
              find = find->left;
            }
          }
          else
          {
            if (find->right == NULL)
            {
              find->right = new_node;
              return;
            }
            else
            {
              //visit right sub-tree
              find = find->right;
            }
          }
        }
      }
    }
    else
    {
      cout << "Memory Overflow";
    }
  }
  void right_leaf_nodes(Node * root)
  {
    if (root != NULL)
    {
      if (root->right != NULL && root->right->right == NULL && root->right->left == NULL)
      {
        //When find right leaf node
        cout << "  " << root->right->data;
      }
      this->right_leaf_nodes(root->left);
      this->right_leaf_nodes(root->right);
    }
  }
};
int main()
{
  BinarySearchTree obj = BinarySearchTree();
  //Add nodes in binary search tree
  /*
             17
          /     \
         4       19
        / \     /  \
       3   10  18   20
          /  \        \
         9    16       37
      */
  obj.add(17);
  obj.add(4);
  obj.add(3);
  obj.add(10);
  obj.add(19);
  obj.add(18);
  obj.add(20);
  obj.add(37);
  obj.add(16);
  obj.add(9);
  obj.right_leaf_nodes(obj.root);
  return 0;
}

Output

  16  37
//Include namespace system
using System;
//C# Program 
//Find right leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
  // Data value 
  public int data;
  // Indicates left and right subtree
  public Node left;
  public Node right;
  public Node(int data)
  {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree
{
  public Node root;
  public BinarySearchTree()
  {
    this.root = null;
  }
  //insert a binary search tree element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(data);
    if (new_node != null)
    {
      if (root == null)
      {
        //When add a first node in BST
        root = new_node;
      }
      else
      {
        Node find = root;
        //Add a new node to its proper position
        while (find != null)
        {
          if (find.data >= data)
          {
            if (find.left == null)
            {
              find.left = new_node;
              return;
            }
            else
            {
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if (find.right == null)
            {
              find.right = new_node;
              return;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      Console.WriteLine("Memory Overflow");
    }
  }
  void right_leaf_nodes(Node root)
  {
    if (root != null)
    {
      if (root.right != null && root.right.right == null && root.right.left == null)
      {
        //When find right leaf node
        Console.Write("  " + root.right.data);
      }
      right_leaf_nodes(root.left);
      right_leaf_nodes(root.right);
    }
  }
  public static void Main(String[] args)
  {
    BinarySearchTree obj = new BinarySearchTree();
    //Add nodes in binary search tree
    /*
               17
            /     \
           4       19
          / \     /  \
         3   10  18   20
            /  \        \
           9    16       37
        */
    obj.add(17);
    obj.add(4);
    obj.add(3);
    obj.add(10);
    obj.add(19);
    obj.add(18);
    obj.add(20);
    obj.add(37);
    obj.add(16);
    obj.add(9);
    obj.right_leaf_nodes(obj.root);
  }
}

Output

  16  37
<?php
//Php Program 
//Find right leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
  // Data value 
  public $data;
  // Indicates left and right subtree
  public $left;
  public $right;

  function __construct($data)
  {
    $this->data = $data;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree
{
  public $root;

  function __construct()
  {
    $this->root = null;
  }
  //insert a binary search tree element
  public  function add($data)
  {
    //Create a dynamic node of binary search tree 
    $new_node = new Node($data);
    if ($new_node != null)
    {
      if ($this->root == null)
      {
        //When add a first node in BST
        $this->root = $new_node;
      }
      else
      {
        $find = $this->root;
        //Add a new node to its proper position
        while ($find != null)
        {
          if ($find->data >= $data)
          {
            if ($find->left == null)
            {
              $find->left = $new_node;
              return;
            }
            else
            {
              //visit left sub-tree
              $find = $find->left;
            }
          }
          else
          {
            if ($find->right == null)
            {
              $find->right = $new_node;
              return;
            }
            else
            {
              //visit right sub-tree
              $find = $find->right;
            }
          }
        }
      }
    }
    else
    {
      echo "Memory Overflow";
    }
  }

  function right_leaf_nodes($root)
  {
    if ($root != null)
    {
      if ($root->right != null && $root->right->right == null && $root->right->left == null)
      {
        echo "  ". $root->right->data;
      }
      $this->right_leaf_nodes($root->left);
      $this->right_leaf_nodes($root->right);
    }
  }
}

function main()
{
  $obj = new BinarySearchTree();
  //Add nodes in binary search tree
  /*
             17
          /     \
         4       19
        / \     /  \
       3   10  18   20
          /  \        \
         9    16       37
      */
  $obj->add(17);
  $obj->add(4);
  $obj->add(3);
  $obj->add(10);
  $obj->add(19);
  $obj->add(18);
  $obj->add(20);
  $obj->add(37);
  $obj->add(16);
  $obj->add(9);
  $obj->right_leaf_nodes($obj->root);
}
main();

Output

  16  37
//Node Js Program 
//Find right leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
  constructor(data)
  {
        // Data value 
    this.data = data;
        // Indicates left and right subtree
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree
{
  constructor()
  {
    this.root = null;
  }
  //insert a binary search tree element
  add(data)
  {
    //Create a dynamic node of binary search tree 
    var new_node = new Node(data);
    if (new_node != null)
    {
      if (this.root == null)
      {
        //When add a first node in BST
        this.root = new_node;
      }
      else
      {
        var find = this.root;
        //Add a new node to its proper position
        while (find != null)
        {
          if (find.data >= data)
          {
            if (find.left == null)
            {
              find.left = new_node;
              return;
            }
            else
            {
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if (find.right == null)
            {
              find.right = new_node;
              return;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      process.stdout.write("Memory Overflow");
    }
  }
  right_leaf_nodes(root)
  {
    if (root != null)
    {
      if (root.right != null && root.right.right == null && root.right.left == null)
      {
        process.stdout.write("  " + root.right.data);
      }
      this.right_leaf_nodes(root.left);
      this.right_leaf_nodes(root.right);
    }
  }
}

function main()
{
  var obj = new BinarySearchTree();
  //Add nodes in binary search tree
  /*
             17
          /     \
         4       19
        / \     /  \
       3   10  18   20
          /  \        \
         9    16       37
      */
  obj.add(17);
  obj.add(4);
  obj.add(3);
  obj.add(10);
  obj.add(19);
  obj.add(18);
  obj.add(20);
  obj.add(37);
  obj.add(16);
  obj.add(9);
  obj.right_leaf_nodes(obj.root);
}
main();

Output

  16  37
# Python 3 Program 
# Find right leaf node in a binary search tree
# Binary Search Tree Node
class Node :
  
  def __init__(self, data) :
      #  Data value 
    self.data = data
    #  Indicates left and right subtree
    self.left = None
    self.right = None
  

class BinarySearchTree :
  
  def __init__(self) :
    self.root = None
  
  # insert a binary search tree element
  def add(self, data) :
    # Create a dynamic node of binary search tree 
    new_node = Node(data)
    if (new_node != None) :
      if (self.root == None) :
        # When add a first node in BST
        self.root = new_node
      else :
        find = self.root
        # Add a new node to its proper position
        while (find != None) :
          if (find.data >= data) :
            if (find.left == None) :
              find.left = new_node
              return
            else :
              # visit left sub-tree
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              return
            else :
              # visit right sub-tree
              find = find.right
            
          
        
      
    else :
      print("Memory Overflow")
    
  
  def right_leaf_nodes(self, root) :
    if (root != None) :
      if (root.right != None and root.right.right == None and root.right.left == None) :
        print(root.right.data, end = "  ")
      
      self.right_leaf_nodes(root.left)
      self.right_leaf_nodes(root.right)
    
  

def main() :
  obj = BinarySearchTree()
  # Add nodes in binary search tree
  # 
  #            17
  #         /     \
  #        4       19
  #       / \     /  \
  #      3   10  18   20
  #         /  \        \
  #        9    16       37
  #     
  
  obj.add(17)
  obj.add(4)
  obj.add(3)
  obj.add(10)
  obj.add(19)
  obj.add(18)
  obj.add(20)
  obj.add(37)
  obj.add(16)
  obj.add(9)
  obj.right_leaf_nodes(obj.root)

if __name__ == "__main__": main()

Output

16  37
# Ruby Program 
# Find right leaf node in a binary search tree
# Binary Search Tree Node
class Node 

  # Define the accessor and reader of class Node  
  attr_reader :data, :left, :right
  attr_accessor :data, :left, :right

  def initialize(data)
    #  Data value 
    self.data = data

    #  Indicates left and right subtree
    self.left = nil
    self.right = nil
  end
end
class BinarySearchTree 

  # Define the accessor and reader of class BinarySearchTree  
  attr_reader :root
  attr_accessor :root
  
  def initialize()
    self.root = nil
  end
  # insert a binary search tree element
  def add(data)
  
    # Create a dynamic node of binary search tree 
    new_node = Node.new(data)
    if (new_node != nil)
    
      if (@root == nil)
      
        # When add a first node in BST
        @root = new_node
      else
      
        find = @root
        # Add a new node to its proper position
        while (find != nil)
        
          if (find.data >= data)
          
            if (find.left == nil)
            
              find.left = new_node
              return
            else
            
              # visit left sub-tree
              find = find.left
            end
          else
          
            if (find.right == nil)
            
              find.right = new_node
              return
            else
            
              # visit right sub-tree
              find = find.right
            end
          end
        end
      end
    else
    
      print("Memory Overflow")
    end
  end
  def right_leaf_nodes(root)
  
    if (root != nil)
    
      if (root.right != nil && root.right.right == nil && root.right.left == nil)
      
        # When find right leaf node
        print("  ", root.right.data)
      end
      self.right_leaf_nodes(root.left)
      self.right_leaf_nodes(root.right)
    end
  end
end
def main()

  obj = BinarySearchTree.new()
  # Add nodes in binary search tree
  # 
  #            17
  #         /     \
  #        4       19
  #       / \     /  \
  #      3   10  18   20
  #         /  \        \
  #        9    16       37
  #     
  
  obj.add(17)
  obj.add(4)
  obj.add(3)
  obj.add(10)
  obj.add(19)
  obj.add(18)
  obj.add(20)
  obj.add(37)
  obj.add(16)
  obj.add(9)
  obj.right_leaf_nodes(obj.root)
end
main()

Output

  16  37
//Scala Program 
//Find right leaf node in a binary search tree
//Binary Search Tree Node
class Node(var data: Int,
  var left: Node,
    var right: Node)
{
  def this(data: Int)
  {
    this(data, null, null);
  }
}
class BinarySearchTree(var root: Node)
{
  def this()
  {
    this(null);
  }
  //insert a binary search tree element
  def add(data: Int): Unit = {
    //Create a dynamic node of binary search tree 
    var new_node: Node = new Node(data);
    if (new_node != null)
    {
      if (root == null)
      {
        //When add a first node in BST
        root = new_node;
      }
      else
      {
        var find: Node = root;
        //Add a new node to its proper position
        while (find != null)
        {
          if (find.data >= data)
          {
            if (find.left == null)
            {
              find.left = new_node;
              return;
            }
            else
            {
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if (find.right == null)
            {
              find.right = new_node;
              return;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      print("Memory Overflow");
    }
  }
  def right_leaf_nodes(root: Node): Unit = {
    if (root != null)
    {
      if (root.right != null && root.right.right == null && root.right.left == null)
      {
        //When find right leaf node
        print("  " + root.right.data);
      }
      right_leaf_nodes(root.left);
      right_leaf_nodes(root.right);
    }
  }
}
object Main
{
  def main(args: Array[String]): Unit = {
    var obj: BinarySearchTree = new BinarySearchTree();
    //Add nodes in binary search tree
    /*
               17
            /     \
           4       19
          / \     /  \
         3   10  18   20
            /  \        \
           9    16       37
        */
    obj.add(17);
    obj.add(4);
    obj.add(3);
    obj.add(10);
    obj.add(19);
    obj.add(18);
    obj.add(20);
    obj.add(37);
    obj.add(16);
    obj.add(9);
    obj.right_leaf_nodes(obj.root);
  }
}

Output

  16  37
//Swift Program 
//Find right leaf node in a binary search tree
//Binary Search Tree Node
class Node
{
  // Data value 
  var data: Int;
  // Indicates left and right subtree
  var left: Node? ;
  var right: Node? ;
  init(_ data: Int)
  {
    self.data = data;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree
{
  var root: Node? ;
  init()
  {
    self.root = nil;
  }
  //insert a binary search tree element
  func add(_ data: Int)
  {
    //Create a dynamic node of binary search tree 
    let new_node: Node? = Node(data);
    if (new_node != nil)
    {
      if (self.root == nil)
      {
        //When add a first node in BST
        self.root = new_node;
      }
      else
      {
        var find: Node? = self.root;
        //Add a new node to its proper position
        while (find != nil)
        {
          if (find!.data >= data)
          {
            if (find!.left == nil)
            {
              find!.left = new_node;
              return;
            }
            else
            {
              //visit left sub-tree
              find = find!.left;
            }
          }
          else
          {
            if (find!.right == nil)
            {
              find!.right = new_node;
              return;
            }
            else
            {
              //visit right sub-tree
              find = find!.right;
            }
          }
        }
      }
    }
    else
    {
      print("Memory Overflow", terminator: "");
    }
  }
  func right_leaf_nodes(_ root: Node? )
  {
    if (root != nil)
    {
      if (root!.right != nil && root!.right!.right == nil && root!.right!.left == nil)
      {
        print("  ", root!.right!.data, terminator: "");
      }
      self.right_leaf_nodes(root!.left);
      self.right_leaf_nodes(root!.right);
    }
  }
}
func main()
{
  let obj: BinarySearchTree = BinarySearchTree();
  //Add nodes in binary search tree
  /*
             17
          /     \
         4       19
        / \     /  \
       3   10  18   20
          /  \        \
         9    16       37
      */
  obj.add(17);
  obj.add(4);
  obj.add(3);
  obj.add(10);
  obj.add(19);
  obj.add(18);
  obj.add(20);
  obj.add(37);
  obj.add(16);
  obj.add(9);
  obj.right_leaf_nodes(obj.root);
}
main();

Output

   16   37




Comment

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