Sun Dec 29 2019 20:06:50 GMT+0000 (UTC)

Posted by @frogblog #java #interviewquestions #search

import java.util.Stack; /** * Java Program to implement a binary search tree. A binary search tree is a * sorted binary tree, where value of a node is greater than or equal to its * left the child and less than or equal to its right child. * * @author WINDOWS 8 * */ public class BST { private static class Node { private int data; private Node left, right; public Node(int value) { data = value; left = right = null; } } private Node root; public BST() { root = null; } public Node getRoot() { return root; } /** * Java function to check if binary tree is empty or not * Time Complexity of this solution is constant O(1) for * best, average and worst case. * * @return true if binary search tree is empty */ public boolean isEmpty() { return null == root; } /** * Java function to return number of nodes in this binary search tree. * Time complexity of this method is O(n) * @return size of this binary search tree */ public int size() { Node current = root; int size = 0; Stack<Node> stack = new Stack<Node>(); while (!stack.isEmpty() || current != null) { if (current != null) { stack.push(current); current = current.left; } else { size++; current = stack.pop(); current = current.right; } } return size; } /** * Java function to clear the binary search tree. * Time complexity of this method is O(1) */ public void clear() { root = null; } }

Copied from tutorial: "It's just a structure, we will subsequently add methods to add a node in a binary search tree, delete a node from binary search tree and find a node from BST in the subsequent part of this binary search tree tutorial. In this implementation, I have created a Node class. It has a data element, an integer and a Node reference to point to another node in the binary tree. I have also created four basic functions, as shown below: getRoot(), returns the root of binary tree isEmpty(), to check if binary search tree is empty or not size(), to find the total number of nodes in a BST clear(), to clear the BST"

https://javarevisited.blogspot.com/2015/10/how-to-implement-binary-search-tree-in-java-example.html#axzz4wnEtnNB3