Print leaf node in Threaded Binary Search Tree

Print leaf node in Threaded BST

Here given code implementation process.

//C Program 
//Print leaf node in Threaded Binary Search Tree
#include <stdio.h>

#include <stdlib.h>
 //Structure of Binary Search Tree node
struct Node {
  int data;
  struct Node *left, *right;
};


struct Node *create_node(int data,
  struct Node *left_side,
  struct Node *right_side) {
  //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 = left_side;
    new_node->right = right_side;

  } else {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  return new_node;
}

//Adding a new node in Threaded Binary Search Tree
struct Node *add_node(struct Node *root,
  struct Node *left_side,
  struct Node *right_side,
  int data) {

  if (root != NULL) {

    if (root->data >= data) {
      if (root->left == left_side) {
        root->left = create_node(data, left_side, root);
      } else {
        root->left = add_node(root->left, left_side, root, data);
      }
    } else if (root->data < data) {
      if (root->right == right_side) {
        root->right = create_node(data, root, right_side);
      } else {
        root->right = add_node(root->right, root, right_side, data);
      }
    }
    return root;
  } else {
    return create_node(data, left_side, right_side);
  }

}
//handling the request of new node insertion 
struct Node *add(struct Node *root, int data) {
  return add_node(root, NULL, NULL, data);
}


void print_leaf(struct Node *root,
  struct Node *left_side,
  struct Node *right_side) {

  if (root != NULL) {
    if (root->left != left_side) {
      print_leaf(root->left, left_side, root);
    }



    if (root->right != right_side) {
      print_leaf(root->right, root, right_side);
    }

    if (root->left == left_side && root->right == right_side)

    {
      printf("%3d", root->data);
    }

  }


}

int main() {

  struct Node *root = NULL;

  //Add nodes in binary search tree
  /*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12


  */


  root = add(root, 5);
  add(root, 3);
  add(root, 9);
  add(root, 1);
  add(root, 4);
  add(root, 8);
  add(root, 11);
  add(root, -3);
  add(root, 2);
  add(root, 7);
  add(root, 12);


  printf("\n Leaf nodes : ");
  print_leaf(root, NULL, NULL);

  return 0;
}

Output

Leaf nodes :  -3  2  4  7 12
/*
  C++ Program
  Print leaf node in Threaded Binary Search Tree
*/
#include<iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left;
  Node *right;
  Node(int value, Node *left_side, Node *right_side) {
    this->data = value;
    this->left = left_side;
    this->right = right_side;
  }
};
class BinarySearchTree {
  public:
  Node *root;
  BinarySearchTree() {
    this->root = NULL;
  }
  Node *add_node(Node *head, Node *left_side, Node *right_side, int value) {
    if (head != NULL) {
      if (head->data >= value) {
        if (head->left == left_side) {
          head->left = new Node(value, left_side, head);
        } else {
          head->left = this->add_node(head->left, left_side, head, value);
        }
      } else
      if (head->data < value) {
        if (head->right == right_side) {
          head->right = new Node(value, head, right_side);
        } else {
          head->right = this->add_node(head->right, head, right_side, value);
        }
      }
      return head;
    } else {
      return new Node(value, left_side, right_side);
    }
  }
  Node *add(int value) {
    return this->add_node(this->root, NULL, NULL, value);
  }
  void print_leaf(Node *head, Node *left_side, Node *right_side) {
    if (head != NULL) {
      if (head->left != left_side) {
        this->print_leaf(head->left, left_side, head);
      }
      if (head->right != right_side) {
        this->print_leaf(head->right, head, right_side);
      }
      if (head->left == left_side && head->right == right_side) {
        cout << head->data << "  ";
      }
    }
  }

};
int main() {
  BinarySearchTree obj ;
  /*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12


  */
  obj.root = obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(4);
  obj.add(8);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(7);
  obj.add(12);
  cout << ("\n Leaf nodes : ");
  obj.print_leaf(obj.root, NULL, NULL);
  return 0;
}

Output

Leaf nodes :  -3  2  4  7 12
//Java program
//Print leaf node in Threaded Binary Search Tree

class Node {
  public int data;
  public Node left;
  public Node right;

  public Node(int value, 
    Node left_side, 
    Node right_side) {
    data = value;
    left = left_side;
    right = right_side;
  }
}
public class BinarySearchTree {


  public Node root;


  BinarySearchTree() {
    root = null;
  }
  //Adding a new node in Threaded Binary Search Tree
  public Node add_node(Node head,
    Node left_side,
    Node right_side,
    int value) {

    if (head != null) {

      if (head.data >= value) {
        if (head.left == left_side) {
          head.left = new Node(value, left_side, head);
        } else {
          head.left = add_node(head.left, left_side, head, value);
        }
      } else if (head.data < value) {
        if (head.right == right_side) {
          head.right = new Node(value, head, right_side);
        } else {
          head.right = add_node(head.right, head, right_side, value);
        }
      }
      return head;
    } else {
      return new Node(value, left_side, right_side);
    }

  }
  //handling the request of new node insertion 
  public Node add(int value) {
    return add_node(root, null, null, value);
  }


  public void print_leaf(Node head, 
    Node left_side, 
    Node right_side) {

    if (head != null) {
      if (head.left != left_side) {
        print_leaf(head.left, left_side, head);
      }
      if (head.right != right_side) {
        print_leaf(head.right, head, right_side);
      }

      if (head.left == left_side && head.right == right_side)
      {
        System.out.print(head.data+"  ");
      }
    }
  }

  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();

    //Add nodes in binary search tree
    /*
           5
         /    \
        3      9
       / \     / \
      1   4   8   11
     / \     /      \
    -3  2   7        12


    */


    obj.root = obj.add(5);
    obj.add(3);
    obj.add(9);
    obj.add(1);
    obj.add(4);
    obj.add(8);
    obj.add(11);
    obj.add(-3);
    obj.add(2);
    obj.add(7);
    obj.add(12);


    System.out.print("\n Leaf nodes : ");
    obj.print_leaf(obj.root, null, null);

  }
}

Output

Leaf nodes :  -3  2  4  7 12
//C# program
//Print leaf node in Threaded Binary Search Tree
using System;
public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int value, 
		Node left_side, 
		Node right_side) {
		data = value;
		left = left_side;
		right = right_side;
	}
}
public class BinarySearchTree {


	public Node root;


	BinarySearchTree() {
		root = null;
	}
	//Adding a new node in Threaded Binary Search Tree
	public Node add_node(Node head,
		Node left_side,
		Node right_side,
		int value) {

		if (head != null) {

			if (head.data >= value) {
				if (head.left == left_side) {
					head.left = new Node(value, left_side, head);
				} else {
					head.left = add_node(head.left, left_side, head, value);
				}
			} else if (head.data < value) {
				if (head.right == right_side) {
					head.right = new Node(value, head, right_side);
				} else {
					head.right = add_node(head.right, head, right_side, value);
				}
			}
			return head;
		} else {
			return new Node(value, left_side, right_side);
		}

	}
	//handling the request of new node insertion 
	public Node add(int value) {
		return add_node(root, null, null, value);
	}


	public void print_leaf(Node head, 
		Node left_side, 
		Node right_side) {

		if (head != null) {
			if (head.left != left_side) {
				print_leaf(head.left, left_side, head);
			}
			if (head.right != right_side) {
				print_leaf(head.right, head, right_side);
			}

			if (head.left == left_side && head.right == right_side)
			{
				Console.Write(head.data+"  ");
			}
		}
	}

	public static void Main(String[] args) {

		BinarySearchTree obj = new BinarySearchTree();

		//Add nodes in binary search tree
		/*
           5
         /    \
        3      9
       / \     / \
      1   4   8   11
     / \     /      \
    -3  2   7        12


    */


		obj.root = obj.add(5);
		obj.add(3);
		obj.add(9);
		obj.add(1);
		obj.add(4);
		obj.add(8);
		obj.add(11);
		obj.add(-3);
		obj.add(2);
		obj.add(7);
		obj.add(12);


		Console.Write("\n Leaf nodes : ");
		obj.print_leaf(obj.root, null, null);

	}
}

Output

Leaf nodes :  -3  2  4  7 12
# Python Program 
# Print leaf node in Threaded Binary Search Tree
class Node :
  
  def __init__(self, value, left_side, right_side) :
    self.data = value
    self.left = left_side
    self.right = right_side
  

class BinarySearchTree :
  
  def __init__(self) :
    self.root = None
  
  def add_node(self, head, left_side, right_side, value) :
    if (head != None) :
      if (head.data >= value) :
        if (head.left == left_side) :
          head.left = Node(value, left_side, head)
        else :
          head.left = self.add_node(head.left, left_side, head, value)
        
      elif (head.data < value) :
        if (head.right == right_side) :
          head.right = Node(value, head, right_side)
        else :
          head.right = self.add_node(head.right, head, right_side, value)
        
      
      return head
    else :
      return Node(value, left_side, right_side)
    
  
  def add(self, value) :
    return self.add_node(self.root, None, None, value)
  
  def print_leaf(self, head, left_side, right_side) :
    if (head != None) :
      if (head.left != left_side) :
        self.print_leaf(head.left, left_side, head)
      
      if (head.right != right_side) :
        self.print_leaf(head.right, head, right_side)
      
      if (head.left == left_side and head.right == right_side) :
        print(head.data ,end="  ")
      
    

def main() :
  obj = BinarySearchTree()
  #
  #             5
  #           /    \
  #          3      9
  #         / \     / \
  #        1   4   8   11
  #       / \     /      \
  #      -3  2   7        12
  #  
  obj.root = obj.add(5)
  obj.add(3)
  obj.add(9)
  obj.add(1)
  obj.add(4)
  obj.add(8)
  obj.add(11)
  obj.add(-3)
  obj.add(2)
  obj.add(7)
  obj.add(12)
  print("\n Leaf nodes :",end=" ")
  obj.print_leaf(obj.root, None, None)
  

if __name__ == "__main__":
  main()

Output

Leaf nodes :  -3  2  4  7 12
# Ruby Program
# Print leaf node in Threaded Binary Search Tree
class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value, left_side, right_side) 
		@data = value
		@left = left_side
		@right = right_side
	end
end

class BinarySearchTree 
	attr_reader :root
	attr_accessor :root
	def initialize() 
		@root = nil
	end
	def add_node(head, left_side, right_side, value) 
		if (head != nil) 
			if (head.data >= value) 
				if (head.left == left_side) 
					head.left = Node.new(value, left_side, head)
				else 
					head.left = self.add_node(head.left, left_side, head, value)
				end
			elsif (head.data < value) 
				if (head.right == right_side) 
					head.right = Node.new(value, head, right_side)
				else 
					head.right = self.add_node(head.right, head, right_side, value)
				end
			end
			return head
		else 
			return Node.new(value, left_side, right_side)
		end
	end
	def add(value) 
		return self.add_node(@root, nil, nil, value)
	end
	def print_leaf(head, left_side, right_side) 
		if (head != nil) 
			if (head.left != left_side) 
				self.print_leaf(head.left, left_side, head)
			end
			if (head.right != right_side) 
				self.print_leaf(head.right, head, right_side)
			end
			if (head.left == left_side and head.right == right_side) 
				print(head.data ,"  ")
			end
		end
	end
end
def main() 
	obj = BinarySearchTree.new()
	#
	#             5
	#           /    \
	#          3      9
	#         / \     / \
	#        1   4   8   11
	#       / \     /      \
	#      -3  2   7        12
	#  
	obj.root = obj.add(5)
	obj.add(3)
	obj.add(9)
	obj.add(1)
	obj.add(4)
	obj.add(8)
	obj.add(11)
	obj.add(-3)
	obj.add(2)
	obj.add(7)
	obj.add(12)
	print("\n Leaf nodes  :")
	obj.print_leaf(obj.root, nil, nil)
end

main()

Output

Leaf nodes :  -3  2  4  7 12
<?php
/*
  Php Program
  Print leaf node in Threaded Binary Search Tree
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value, $left_side, $right_side) {
    $this->data = $value;
    $this->left = $left_side;
    $this->right = $right_side;
  }
}
class BinarySearchTree {
  public $root;

  function __construct() {
    $this->root = null;
  }
  public  function add_node($head, $left_side, $right_side, $value) {
    if ($head != null) {
      if ($head->data >= $value) {
        if ($head->left == $left_side) {
          $head->left = new Node($value, $left_side, $head);
        } else {
          $head->left = $this->add_node($head->left, $left_side, $head, $value);
        }
      } else
      if ($head->data < $value) {
        if ($head->right == $right_side) {
          $head->right = new Node($value, $head, $right_side);
        } else {
          $head->right = $this->add_node($head->right, $head, $right_side, $value);
        }
      }
      return $head;
    } else {
      return new Node($value, $left_side, $right_side);
    }
  }
  public  function add($value) {
    return $this->add_node($this->root, null, null, $value);
  }
  public  function print_leaf($head, $left_side, $right_side) {
    if ($head != null) {
      if ($head->left != $left_side) {
        $this->print_leaf($head->left, $left_side, $head);
      }
      if ($head->right != $right_side) {
        $this->print_leaf($head->right, $head, $right_side);
      }
      if ($head->left == $left_side && $head->right == $right_side) {
        echo ($head->data ."  ");
      }
    }
  }

}
function main() {
  $obj = new BinarySearchTree();
  /*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12


  */
  $obj->root =
  $obj->add(5);
  $obj->add(3);
  $obj->add(9);
  $obj->add(1);
  $obj->add(4);
  $obj->add(8);
  $obj->add(11);
  $obj->add(-3);
  $obj->add(2);
  $obj->add(7);
  $obj->add(12);
  echo("\n Leaf nodes : ");
  $obj->print_leaf($obj->root, null, null);
}
main();

Output

Leaf nodes :  -3  2  4  7 12
/*
  Node JS Program
  Print leaf node in Threaded Binary Search Tree
*/
class Node {
	
	constructor(value, left_side, right_side) {
		this.data = value;
		this.left = left_side;
		this.right = right_side;
	}
}
class BinarySearchTree {
	
	constructor() {
		this.root = null;
	}
	add_node(head, left_side, right_side, value) {
		if (head != null) {
			if (head.data >= value) {
				if (head.left == left_side) {
					head.left = new Node(value, left_side, head);
				} else {
					head.left = this.add_node(head.left, left_side, head, value);
				}
			} else
			if (head.data < value) {
				if (head.right == right_side) {
					head.right = new Node(value, head, right_side);
				} else {
					head.right = this.add_node(head.right, head, right_side, value);
				}
			}
			return head;
		} else {
			return new Node(value, left_side, right_side);
		}
	}
	add(value) {
		return this.add_node(this.root, null, null, value);
	}
	print_leaf(head, left_side, right_side) {
		if (head != null) {
			if (head.left != left_side) {
				this.print_leaf(head.left, left_side, head);
			}
			if (head.right != right_side) {
				this.print_leaf(head.right, head, right_side);
			}
			if (head.left == left_side && head.right == right_side) {
				process.stdout.write(head.data + "  ");
			}
		}
	}
}
function main() {
	var obj = new BinarySearchTree();
	/*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12


   */
	obj.root = obj.add(5);
	obj.add(3);
	obj.add(9);
	obj.add(1);
	obj.add(4);
	obj.add(8);
	obj.add(11);
	obj.add(-3);
	obj.add(2);
	obj.add(7);
	obj.add(12);
	process.stdout.write("\n Leaf nodes : ");
	obj.print_leaf(obj.root, null, null);
}
main();

Output

Leaf nodes :  -3  2  4  7 12
/*
  Swift 4 Program
  Print leaf node in Threaded Binary Search Tree
*/
class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int, _ left_side: Node? , _ right_side : Node? ) {
    self.data = value;
    self.left = left_side;
    self.right = right_side;
  }
}
class BinarySearchTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func add_node(_ head: Node? , _ left_side : Node? , _ right_side : Node? , _ value : Int) -> Node? {
    if (head != nil) {
      if (head!.data >= value) {
        if (head!.left === left_side) {
          head!.left = Node(value, left_side, head);
        } else {
          head!.left = self.add_node(head!.left, left_side, head, value);
        }
      } else
      if (head!.data < value) {
        if (head!.right === right_side) {
          head!.right = Node(value, head, right_side);
        } else {
          head!.right = self.add_node(head!.right, head, right_side, value);
        }
      }
      return head;
    } else {
      return Node(value, left_side, right_side);
    }
  }
  func add(_ value: Int) {
    let new_node = self.add_node(self.root, nil, nil, value);
    if(self.root==nil)
    {
      self.root = new_node;
    }
  }
  func print_leaf(_ head: Node? , _ left_side : Node? , _ right_side : Node? ) {
    if (head != nil) {
      if (!(head!.left === left_side)) {
        self.print_leaf(head!.left, left_side, head);
      }
      if (!(head!.right === right_side)) {
        self.print_leaf(head!.right, head, right_side);
      }
      if (head!.left === left_side && head!.right === right_side) {
        print(head!.data ,terminator:"  ");
      }
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  /*
             5
           /    \
          3      9
         / \     / \
        1   4   8   11
       / \     /      \
      -3  2   7        12


  */
  obj.add(5);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(4);
  obj.add(8);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(7);
  obj.add(12);
  print("\n Leaf nodes :",terminator:"  ");
  obj.print_leaf(obj.root, nil, nil);
}
main();

Output

Leaf nodes :  -3  2  4  7 12


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