Binary Search Tree
| Space | Time | |||
|---|---|---|---|---|
| Access | Lookup | Insertion | Deletion | |
O(n) | O(log n) | O(log n) | O(log n) | O(log n) |
Definition​
- Short
- Detailed
Binary Search Tree is a data structure that organizes elements in a sorted manner, where each node can have at most 2 children: a left and a right child. This makes it efficient for searching, insertion, and deletion operations.
Simplified
Binary Search Tree is like a library system. Each book (or "node") has a unique identifier and up to 2 related books. You start from a certain point (the "root") and go left if the book you're looking for has a smaller identifier, right if it's larger. This way, you eliminate half of the remaining books with each step, making the search efficient.
Binary Search Trees (BSTs) are data structures that store items like numbers or names in memory. They're used for quick lookup, addition, and removal of items, and can be used to create dynamic sets of items or lookup tables.
BSTs maintain their keys in sorted order, allowing operations to use binary search principles. When searching for a key or a place to insert a new key, they traverse the tree from root to leaf, comparing keys stored in the nodes and deciding to continue searching in the left or right subtrees based on the comparison.
On average, each comparison lets the operations skip about half of the tree, making each lookup, insertion, or deletion time proportional to the logarithm of the number of items in the tree. This is faster than the linear time needed to find items by key in an unsorted array, but slower than operations on hash tables.
Practice​
- Practice
- Solution
| Aspect | Pseudo Code |
|---|---|
| Insertion | |
| Search Node | |
| Find MIN | |
| Find MAX | |
| Find Successor | |
| Find Predecessor | |
| Deletion | |
| BFS Recursive | |
| BFS Iterative | |
| DFS PreOrder Recursive | |
| DFS PreOrder Iterative | |
| DFS InOrder Recursive | |
| DFS InOrder Iterative | |
| DFS PostOrder Recursive | |
| DFS PostOrder Iterative | |
package main
type Node struct {
Key int
Left *Node
Right *Node
}
type BinarySearchTree struct {
Root *Node
}
func (bst *BinarySearchTree) insert(root *Node, key int) *Node {
if root == nil {
return &Node{Key: key}
}
if key < root.Key {
root.Left = bst.insert(root.Left, key)
} else if key > root.Key {
root.Right = bst.insert(root.Right, key)
}
return root
}
func (bst *BinarySearchTree) search(root *Node, key int) *Node {
if root == nil || root.Key == key {
return root
}
if key < root.Key {
return bst.search(root.Left, key)
} else {
return bst.search(root.Right, key)
}
}
func (bst *BinarySearchTree) findMin(root *Node) *Node {
current := root
for current != nil && current.Left != nil {
current = current.Left
}
return current
}
func (bst *BinarySearchTree) findMax(root *Node) *Node {
current := root
for current != nil && current.Right != nil {
current = current.Right
}
return current
}
func (bst *BinarySearchTree) findSuccessor(root *Node, key int) *Node {
if root == nil {
return nil
}
var successor *Node
current := root
for current != nil {
if key < current.Key {
successor = current
current = current.Left
} else {
current = current.Right
}
}
return successor
}
func (bst *BinarySearchTree) findPredecessor(root *Node, key int) *Node {
if root == nil {
return nil
}
var predecessor *Node
current := root
for current != nil {
if key > current.Key {
predecessor = current
current = current.Right
} else {
current = current.Left
}
}
return predecessor
}
func (bst *BinarySearchTree) deleteNode(root *Node, key int) *Node {
if root == nil {
return nil
}
if key < root.Key {
root.Left = bst.deleteNode(root.Left, key)
} else if key > root.Key {
root.Right = bst.deleteNode(root.Right, key)
} else {
if root.Left == nil {
return root.Right
} else if root.Right == nil {
return root.Left
}
successor := bst.findMin(root.Right)
root.Key = successor.Key
root.Right = bst.deleteNode(root.Right, successor.Key)
}
return root
}
func (bst *BinarySearchTree) bfsRecursive(root *Node) {
if root == nil {
return
}
queue := []*Node{root}
bst.bfsHelper(queue)
}
func (bst *BinarySearchTree) bfsHelper(queue []*Node) {
if len(queue) == 0 {
return
}
current := queue[0]
queue = queue[1:]
fmt.Println(current.Key)
if current.Left != nil {
queue = append(queue, current.Left)
}
if current.Right != nil {
queue = append(queue, current.Right)
}
bst.bfsHelper(queue)
}
func (bst *BinarySearchTree) bfsIterative(root *Node) {
if root == nil {
return
}
queue := []*Node{root}
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
fmt.Println(current.Key)
if current.Left != nil {
queue = append(queue, current.Left)
}
if current.Right != nil {
queue = append(queue, current.Right)
}
}
}
func (bst *BinarySearchTree) dfsPreOrderRecursive(root *Node) {
if root == nil {
return
}
fmt.Println(root.Key)
bst.dfsPreOrderRecursive(root.Left)
bst.dfsPreOrderRecursive(root.Right)
}
func (bst *BinarySearchTree) dfsPreOrderIterative(root *Node) {
if root == nil {
return
}
stack := []*Node{root}
for len(stack) > 0 {
current := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(current.Key)
if current.Right != nil {
stack = append(stack, current.Right)
}
if current.Left != nil {
stack = append(stack, current.Left)
}
}
}
func (bst *BinarySearchTree) dfsInOrderRecursive(root *Node) {
if root == nil {
return
}
bst.dfsInOrderRecursive(root.Left)
fmt.Println(root.Key)
bst.dfsInOrderRecursive(root.Right)
}
func (bst *BinarySearchTree) dfsInOrderIterative(root *Node) {
if root == nil {
return
}
stack := []*Node{}
current := root
for current != nil || len(stack) > 0 {
for current != nil {
stack = append(stack, current)
current = current.Left
}
current = stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(current.Key)
current = current.Right
}
}
func (bst *BinarySearchTree) dfsPostOrderRecursive(root *Node) {
if root == nil {
return
}
bst.dfsPostOrderRecursive(root.Left)
bst.dfsPostOrderRecursive(root.Right)
fmt.Println(root.Key)
}
func (bst *BinarySearchTree) dfsPostOrderIterative(root *Node) {
if root == nil {
return
}
stack1 := []*Node{}
stack2 := []*Node{root}
for len(stack2) > 0 {
current := stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
stack1 = append(stack1, current)
if current.Left != nil {
stack2 = append(stack2, current.Left)
}
if current.Right != nil {
stack2 = append(stack2, current.Right)
}
}
for len(stack1) > 0 {
current := stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
fmt.Println(current.Key)
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinarySearchTree {
private Node root;
public Node insert(Node root, int key) {
if (root == null) {
return new Node(key);
}
if (key < root.key) {
root.left = insert(root.left, key);
} else if (key > root.key) {
root.right = insert(root.right, key);
}
return root;
}
public Node search(Node root, int key) {
if (root == null || root.key == key) {
return root;
}
return (key < root.key) ? search(root.left, key) : search(root.right, key);
}
public Node findMin(Node root) {
Node current = root;
while (current != null && current.left != null) {
current = current.left;
}
return current;
}
public Node findMax(Node root) {
Node current = root;
while (current != null && current.right != null) {
current = current.right;
}
return current;
}
public Node findSuccessor(Node root, int key) {
if (root == null) {
return null;
}
Node current = root;
Node successor = null;
while (current != null) {
if (key < current.key) {
successor = current;
current = current.left;
} else {
current = current.right;
}
}
return successor;
}
public Node findPredecessor(Node root, int key) {
if (root == null) {
return null;
}
Node current = root;
Node predecessor = null;
while (current != null) {
if (key > current.key) {
predecessor = current;
current = current.right;
} else {
current = current.left;
}
}
return predecessor;
}
public Node deleteNode(Node root, int key) {
if (root == null) {
return null;
}
if (key < root.key) {
root.left = deleteNode(root.left, key);
} else if (key > root.key) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
Node successor = findMin(root.right);
root.key = successor.key;
root.right = deleteNode(root.right, successor.key);
}
return root;
}
public void bfsRecursive(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
bfsHelper(queue);
}
private void bfsHelper(Queue<Node> queue) {
if (queue.isEmpty()) {
return;
}
Node current = queue.poll();
System.out.println(current.key);
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
bfsHelper(queue);
}
public void bfsIterative(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.println(current.key);
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
}
public void dfsPreOrderRecursive(Node root) {
if (root == null) {
return;
}
System.out.println(root.key);
dfsPreOrderRecursive(root.left);
dfsPreOrderRecursive(root.right);
}
public void dfsPreOrderIterative(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node current = stack.pop();
System.out.println(current.key);
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
public void dfsInOrderRecursive(Node root) {
if (root == null) {
return;
}
dfsInOrderRecursive(root.left);
System.out.println(root.key);
dfsInOrderRecursive(root.right);
}
public void dfsInOrderIterative(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
System.out.println(current.key);
current = current.right;
}
}
public void dfsPostOrderRecursive(Node root) {
if (root == null) {
return;
}
dfsPostOrderRecursive(root.left);
dfsPostOrderRecursive(root.right);
System.out.println(root.key);
}
public void dfsPostOrderIterative(Node root) {
if (root == null) {
return;
}
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
Node current = stack1.pop();
stack2.push(current);
if (current.left != null) {
stack1.push(current.left);
}
if (current.right != null) {
stack1.push(current.right);
}
}
while (!stack2.isEmpty()) {
System.out.println(stack2.pop().key);
}
}
public static class Node {
int key;
Node left;
Node right;
public Node(int key) {
this.key = key;
}
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(root, key) {
if (root === null) {
return { key, left: null, right: null };
}
if (key < root.key) {
root.left = this.insert(root.left, key);
} else if (key > root.key) {
root.right = this.insert(root.right, key);
}
return root;
}
search(root, key) {
if (root === null || root.key === key) {
return root;
}
return key < root.key
? this.search(root.left, key)
: this.search(root.right, key);
}
findMin(root) {
let current = root;
while (current && current.left !== null) {
current = current.left;
}
return current;
}
findMax(root) {
let current = root;
while (current && current.right !== null) {
current = current.right;
}
return current;
}
findSuccessor(root, key) {
if (root === null) {
return null;
}
let current = root;
let successor = null;
while (current !== null) {
if (key < current.key) {
successor = current;
current = current.left;
} else {
current = current.right;
}
}
return successor;
}
findPredecessor(root, key) {
if (root === null) {
return null;
}
let current = root;
let predecessor = null;
while (current !== null) {
if (key > current.key) {
predecessor = current;
current = current.right;
} else {
current = current.left;
}
}
return predecessor;
}
deleteNode(root, key) {
if (root === null) {
return null;
}
if (key < root.key) {
root.left = this.deleteNode(root.left, key);
} else if (key > root.key) {
root.right = this.deleteNode(root.right, key);
} else {
if (root.left === null) {
return root.right;
} else if (root.right === null) {
return root.left;
}
const successor = this.findMin(root.right);
root.key = successor ? successor.key : 0;
root.right = this.deleteNode(root.right, successor ? successor.key : 0);
}
return root;
}
bfsRecursive(root) {
if (root === null) {
return;
}
const queue = [root];
this.bfsHelper(queue);
}
bfsHelper(queue) {
if (queue.length === 0) {
return;
}
const current = queue.shift();
console.log(current.key);
current.left && queue.push(current.left);
current.right && queue.push(current.right);
this.bfsHelper(queue);
}
bfsIterative(root) {
if (root === null) {
return;
}
const queue = [root];
while (queue.length > 0) {
const current = queue.shift();
console.log(current.key);
current.left && queue.push(current.left);
current.right && queue.push(current.right);
}
}
dfsPreOrderRecursive(root) {
if (root === null) {
return;
}
console.log(root.key);
this.dfsPreOrderRecursive(root.left);
this.dfsPreOrderRecursive(root.right);
}
dfsPreOrderIterative(root) {
if (root === null) {
return;
}
const stack = [root];
while (stack.length > 0) {
const current = stack.pop();
console.log(current.key);
current.right && stack.push(current.right);
current.left && stack.push(current.left);
}
}
dfsInOrderRecursive(root) {
if (root === null) {
return;
}
this.dfsInOrderRecursive(root.left);
console.log(root.key);
this.dfsInOrderRecursive(root.right);
}
dfsInOrderIterative(root) {
if (root === null) {
return;
}
const stack = [];
let current = root;
while (current !== null || stack.length > 0) {
while (current !== null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
console.log(current.key);
current = current.right;
}
}
dfsPostOrderRecursive(root) {
if (root === null) {
return;
}
this.dfsPostOrderRecursive(root.left);
this.dfsPostOrderRecursive(root.right);
console.log(root.key);
}
dfsPostOrderIterative(root) {
if (root === null) {
return;
}
const stack1 = [];
const stack2 = [];
stack1.push(root);
while (stack1.length > 0) {
const current = stack1.pop();
stack2.push(current);
current.left && stack1.push(current.left);
current.right && stack1.push(current.right);
}
while (stack2.length > 0) {
console.log(stack2.pop().key);
}
}
}
class BinarySearchTree {
data class Node(var key: Int, var left: Node? = null, var right: Node? = null)
var root: Node? = null
fun insert(root: Node?, key: Int): Node {
if (root == null) {
return Node(key)
}
if (key < root.key) {
root.left = insert(root.left, key)
} else if (key > root.key) {
root.right = insert(root.right, key)
}
return root
}
fun search(root: Node?, key: Int): Node? {
if (root == null || root.key == key) {
return root
}
return if (key < root.key) {
search(root.left, key)
} else {
search(root.right, key)
}
}
fun findMin(root: Node?): Node? {
var current = root
while (current?.left != null) {
current = current.left
}
return current
}
fun findMax(root: Node?): Node? {
var current = root
while (current?.right != null) {
current = current.right
}
return current
}
fun findSuccessor(root: Node?, key: Int): Node? {
if (root == null) {
return null
}
var current = root
var successor: Node? = null
while (current != null) {
if (key < current.key) {
successor = current
current = current.left
} else {
current = current.right
}
}
return successor
}
fun findPredecessor(root: Node?, key: Int): Node? {
if (root == null) {
return null
}
var current = root
var predecessor: Node? = null
while (current != null) {
if (key > current.key) {
predecessor = current
current = current.right
} else {
current = current.left
}
}
return predecessor
}
fun deleteNode(root: Node?, key: Int): Node? {
if (root == null) {
return null
}
if (key < root.key) {
root.left = deleteNode(root.left, key)
} else if (key > root.key) {
root.right = deleteNode(root.right, key)
} else {
if (root.left == null) {
return root.right
} else if (root.right == null) {
return root.left
}
val successor = findMin(root.right)
root.key = successor?.key ?: 0
root.right = deleteNode(root.right, successor?.key ?: 0)
}
return root
}
fun bfsRecursive(root: Node?) {
if (root == null) {
return
}
val queue = mutableListOf<Node?>()
queue.add(root)
bfsHelper(queue)
}
private fun bfsHelper(queue: MutableList<Node?>) {
if (queue.isEmpty()) {
return
}
val current = queue.removeAt(0)
println(it.key)
current?.left?.let { queue.add(it) }
current?.right?.let { queue.add(it) }
bfsHelper(queue)
}
fun bfsIterative(root: Node?) {
if (root == null) {
return
}
val queue = mutableListOf<Node?>()
queue.add(root)
while (queue.isNotEmpty()) {
val current = queue.removeAt(0)
println(it.key)
current?.left?.let { queue.add(it) }
current?.right?.let { queue.add(it) }
}
}
fun dfsPreOrderRecursive(root: Node?) {
if (root == null) {
return
}
println(it.key)
dfsPreOrderRecursive(root.left)
dfsPreOrderRecursive(root.right)
}
fun dfsPreOrderIterative(root: Node?) {
if (root == null) {
return
}
val stack = mutableListOf<Node?>()
stack.add(root)
while (stack.isNotEmpty()) {
val current = stack.removeAt(stack.size - 1)
println(it.key)
current?.right?.let { stack.add(it) }
current?.left?.let { stack.add(it) }
}
}
fun dfsInOrderRecursive(root: Node?) {
if (root == null) {
return
}
dfsInOrderRecursive(root.left)
println(it.key)
dfsInOrderRecursive(root.right)
}
fun dfsInOrderIterative(root: Node?) {
if (root == null) {
return
}
val stack = mutableListOf<Node?>()
var current = root
while (current != null || stack.isNotEmpty()) {
while (current != null) {
stack.add(current)
current = current.left
}
current = stack.removeAt(stack.size - 1)
println(it.key)
current = current.right
}
}
fun dfsPostOrderRecursive(root: Node?) {
if (root == null) {
return
}
dfsPostOrderRecursive(root.left)
dfsPostOrderRecursive(root.right)
println(it.key)
}
fun dfsPostOrderIterative(root: Node?) {
if (root == null) {
return
}
val stack1 = mutableListOf<Node?>()
val stack2 = mutableListOf<Node?>()
stack1.add(root)
while (stack1.isNotEmpty()) {
val current = stack1.removeAt(stack1.size - 1)
stack2.add(current)
current?.left?.let { stack1.add(it) }
current?.right?.let { stack1.add(it) }
}
while (stack2.isNotEmpty()) {
println(it.key)
}
}
}
class BinarySearchTree:
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def __init__(self):
self.root = None
def insert(self, root, key):
if root is None:
return self.Node(key)
if key < root.key:
root.left = self.insert(root.left, key)
elif key > root.key:
root.right = self.insert(root.right, key)
return root
def search(self, root, key):
if root is None or root.key == key:
return root
return self.search(root.left, key) if key < root.key else self.search(root.right, key)
def find_min(self, root):
current = root
while current and current.left is not None:
current = current.left
return current
def find_max(self, root):
current = root
while current and current.right is not None:
current = current.right
return current
def find_successor(self, root, key):
if root is None:
return None
current, successor = root, None
while current is not None:
if key < current.key:
successor = current
current = current.left
else:
current = current.right
return successor
def find_predecessor(self, root, key):
if root is None:
return None
current, predecessor = root, None
while current is not None:
if key > current.key:
predecessor = current
current = current.right
else:
current = current.left
return predecessor
def delete_node(self, root, key):
if root is None:
return None
if key < root.key:
root.left = self.delete_node(root.left, key)
elif key > root.key:
root.right = self.delete_node(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
successor = self.find_min(root.right)
root.key = successor.key
root.right = self.delete_node(root.right, successor.key)
return root
def bfs_recursive(self, root):
if root is None:
return
queue = [root]
self.bfs_helper(queue)
def bfs_helper(self, queue):
if not queue:
return
current = queue.pop(0)
print(current.key)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
self.bfs_helper(queue)
def bfs_iterative(self, root):
if root is None:
return
queue = [root]
while queue:
current = queue.pop(0)
print(current.key)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
def dfs_pre_order_recursive(self, root):
if root is None:
return
print(root.key)
self.dfs_pre_order_recursive(root.left)
self.dfs_pre_order_recursive(root.right)
def dfs_pre_order_iterative(self, root):
if root is None:
return
stack = [root]
while stack:
current = stack.pop()
print(current.key)
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
def dfs_in_order_recursive(self, root):
if root is None:
return
self.dfs_in_order_recursive(root.left)
print(root.key)
self.dfs_in_order_recursive(root.right)
def dfs_in_order_iterative(self, root):
if root is None:
return
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
print(current.key)
current = current.right
def dfs_post_order_recursive(self, root):
if root is None:
return
self.dfs_post_order_recursive(root.left)
self.dfs_post_order_recursive(root.right)
print(root.key)
def dfs_post_order_iterative(self, root):
if root is None:
return
stack1 = []
stack2 = []
stack1.append(root)
while stack1:
current = stack1.pop()
stack2.append(current)
if current.left:
stack1.append(current.left)
if current.right:
stack1.append(current.right)
while stack2:
print(stack2.pop().key)
use std::collections::VecDeque;
#[derive(Debug)]
struct Node {
key: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>,
}
impl Node {
fn new(key: i32) -> Self {
Node {
key,
left: None,
right: None,
}
}
}
#[derive(Debug)]
struct BinarySearchTree {
root: Option<Box<Node>>,
}
impl BinarySearchTree {
fn new() -> Self {
BinarySearchTree { root: None }
}
fn insert(&mut self, root: Option<Box<Node>>, key: i32) -> Box<Node> {
if let Some(mut node) = root {
if key < node.key {
node.left = Some(self.insert(node.left.take(), key));
} else if key > node.key {
node.right = Some(self.insert(node.right.take(), key));
}
node
} else {
Box::new(Node::new(key))
}
}
fn search(&self, root: &Option<Box<Node>>, key: i32) -> Option<&Box<Node>> {
match root {
Some(node) => {
if node.key == key {
Some(node)
} else if key < node.key {
self.search(&node.left, key)
} else {
self.search(&node.right, key)
}
}
None => None,
}
}
fn find_min(&self, root: &Option<Box<Node>>) -> Option<&Box<Node>> {
let mut current = root;
while let Some(node) = current {
if let Some(left_node) = &node.left {
current = Some(left_node);
} else {
return Some(node);
}
}
None
}
fn find_max(&self, root: &Option<Box<Node>>) -> Option<&Box<Node>> {
let mut current = root;
while let Some(node) = current {
if let Some(right_node) = &node.right {
current = Some(right_node);
} else {
return Some(node);
}
}
None
}
fn find_successor(&self, root: &Option<Box<Node>>, key: i32) -> Option<&Box<Node>> {
let mut current = root;
let mut successor = None;
while let Some(node) = current {
if key < node.key {
successor = Some(node);
current = Some(&node.left);
} else {
current = Some(&node.right);
}
}
successor
}
fn find_predecessor(&self, root: &Option<Box<Node>>, key: i32) -> Option<&Box<Node>> {
let mut current = root;
let mut predecessor = None;
while let Some(node) = current {
if key > node.key {
predecessor = Some(node);
current = Some(&node.right);
} else {
current = Some(&node.left);
}
}
predecessor
}
fn delete_node(&mut self, root: Option<Box<Node>>, key: i32) -> Option<Box<Node>> {
if let Some(mut node) = root {
if key < node.key {
node.left = self.delete_node(node.left.take(), key);
} else if key > node.key {
node.right = self.delete_node(node.right.take(), key);
} else {
if node.left.is_none() {
return node.right;
} else if node.right.is_none() {
return node.left;
}
if let Some(successor) = self.find_min(&node.right) {
node.key = successor.key;
node.right = self.delete_node(node.right.take(), successor.key);
}
}
Some(node)
} else {
None
}
}
fn bfs_recursive(&self, root: &Option<Box<Node>>) {
if let Some(node) = root {
let mut queue = VecDeque::new();
queue.push_back(node);
self.bfs_helper(&queue);
}
}
fn bfs_helper(&self, queue: &VecDeque<&Box<Node>>) {
let mut queue = queue.clone();
if let Some(current) = queue.pop_front() {
println!("{}", current.key);
if let Some(left_node) = ¤t.left {
queue.push_back(left_node);
}
if let Some(right_node) = ¤t.right {
queue.push_back(right_node);
}
self.bfs_helper(&queue);
}
}
fn bfs_iterative(&self, root: &Option<Box<Node>>) {
if let Some(node) = root {
let mut queue = VecDeque::new();
queue.push_back(node);
while let Some(current) = queue.pop_front() {
println!("{}", current.key);
if let Some(left_node) = ¤t.left {
queue.push_back(left_node);
}
if let Some(right_node) = ¤t.right {
queue.push_back(right_node);
}
}
}
}
fn dfs_pre_order_recursive(&self, root: &Option<Box<Node>>) {
if let Some(node) = root {
println!("{}", node.key);
self.dfs_pre_order_recursive(&node.left);
self.dfs_pre_order_recursive(&node.right);
}
}
fn dfs_pre_order_iterative(&self, root: &Option<Box<Node>>) {
if let Some(node) = root {
let mut stack = vec![node];
while let Some(current) = stack.pop() {
println!("{}", current.key);
if let Some(right_node) = ¤t.right {
stack.push(right_node);
}
if let Some(left_node) = ¤t.left {
stack.push(left_node);
}
}
}
}
fn dfs_in_order_recursive(&self, root: &Option<Box<Node>>) {
if let Some(node) = root {
self.dfs_in_order_recursive(&node.left);
println!("{}", node.key);
self.dfs_in_order_recursive(&node.right);
}
}
fn dfs_in_order_iterative(&self, root: &Option<Box<Node>>) {
let mut stack = Vec::new();
let mut current = root;
while let Some(node) = current {
stack.push(node);
current = &node.left;
}
while let Some(node) = stack.pop() {
println!("{}", node.key);
current = &node.right;
while let Some(node) = current {
stack.push(node);
current = &node.left;
}
}
}
fn dfs_post_order_recursive(&self, root: &Option<Box<Node>>) {
if let Some(node) = root {
self.dfs_post_order_recursive(&node.left);
self.dfs_post_order_recursive(&node.right);
println!("{}", node.key);
}
}
fn dfs_post_order_iterative(&self, root: &Option<Box<Node>>) {
if let Some(node) = root {
let mut stack1 = Vec::new();
let mut stack2 = Vec::new();
stack1.push(node);
while let Some(current) = stack1.pop() {
stack2.push(current.clone());
if let Some(left_node) = ¤t.left {
stack1.push(left_node
class Node {
key: number;
left: Node | null;
right: Node | null;
constructor(
key: number,
left: Node | null = null,
right: Node | null = null,
) {
this.key = key;
this.left = left;
this.right = right;
}
}
class BinarySearchTree {
root: Node | null;
constructor() {
this.root = null;
}
insert(root: Node | null, key: number): Node {
if (root === null) {
return new Node(key);
}
if (key < root.key) {
root.left = this.insert(root.left, key);
} else if (key > root.key) {
root.right = this.insert(root.right, key);
}
return root;
}
search(root: Node | null, key: number): Node | null {
if (root === null || root.key === key) {
return root;
}
return key < root.key
? this.search(root.left, key)
: this.search(root.right, key);
}
findMin(root: Node | null): Node | null {
let current = root;
while (current?.left !== null) {
current = current.left;
}
return current;
}
findMax(root: Node | null): Node | null {
let current = root;
while (current?.right !== null) {
current = current.right;
}
return current;
}
findSuccessor(root: Node | null, key: number): Node | null {
if (root === null) {
return null;
}
let current: Node | null = root;
let successor: Node | null = null;
while (current !== null) {
if (key < current.key) {
successor = current;
current = current.left;
} else {
current = current.right;
}
}
return successor;
}
findPredecessor(root: Node | null, key: number): Node | null {
if (root === null) {
return null;
}
let current: Node | null = root;
let predecessor: Node | null = null;
while (current !== null) {
if (key > current.key) {
predecessor = current;
current = current.right;
} else {
current = current.left;
}
}
return predecessor;
}
deleteNode(root: Node | null, key: number): Node | null {
if (root === null) {
return null;
}
if (key < root.key) {
root.left = this.deleteNode(root.left, key);
} else if (key > root.key) {
root.right = this.deleteNode(root.right, key);
} else {
if (root.left === null) {
return root.right;
} else if (root.right === null) {
return root.left;
}
const successor = this.findMin(root.right);
root.key = successor?.key || 0;
root.right = this.deleteNode(root.right, successor?.key || 0);
}
return root;
}
bfsRecursive(root: Node | null): void {
if (root === null) {
return;
}
const queue: (Node | null)[] = [root];
this.bfsHelper(queue);
}
bfsIterative(root: Node | null): void {
if (root === null) {
return;
}
const queue: (Node | null)[] = [root];
while (queue.length > 0) {
const current = queue.shift();
if (current !== undefined) {
console.log(current.key);
if (current.left !== null) {
queue.push(current.left);
}
if (current.right !== null) {
queue.push(current.right);
}
}
}
}
dfsPreOrderRecursive(root: Node | null): void {
if (root === null) {
return;
}
console.log(root.key);
this.dfsPreOrderRecursive(root.left);
this.dfsPreOrderRecursive(root.right);
}
dfsPreOrderIterative(root: Node | null): void {
if (root === null) {
return;
}
const stack: (Node | null)[] = [root];
while (stack.length > 0) {
const current = stack.pop();
if (current !== undefined) {
console.log(current.key);
if (current.right !== null) {
stack.push(current.right);
}
if (current.left !== null) {
stack.push(current.left);
}
}
}
}
dfsInOrderRecursive(root: Node | null): void {
if (root === null) {
return;
}
this.dfsInOrderRecursive(root.left);
console.log(root.key);
this.dfsInOrderRecursive(root.right);
}
dfsInOrderIterative(root: Node | null): void {
if (root === null) {
return;
}
const stack: (Node | null)[] = [];
let current: Node | null = root;
while (current !== null || stack.length > 0) {
while (current !== null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
if (current !== undefined) {
console.log(current.key);
current = current.right;
}
}
}
dfsPostOrderRecursive(root: Node | null): void {
if (root === null) {
return;
}
this.dfsPostOrderRecursive(root.left);
this.dfsPostOrderRecursive(root.right);
console.log(root.key);
}
dfsPostOrderIterative(root: Node | null): void {
if (root === null) {
return;
}
const stack1: (Node | null)[] = [];
const stack2: (Node | null)[] = [];
stack1.push(root);
while (stack1.length > 0) {
const current = stack1.pop();
if (current !== undefined) {
stack2.push(current);
if (current.left !== null) {
stack1.push(current.left);
}
if (current.right !== null) {
stack1.push(current.right);
}
}
}
while (stack2.length > 0) {
const current = stack2.pop();
if (current !== undefined) {
console.log(current.key);
}
}
}
private bfsHelper(queue: (Node | null)[]): void {
if (queue.length === 0) {
return;
}
const current = queue.shift();
if (current !== undefined) {
console.log(current.key);
if (current.left !== null) {
queue.push(current.left);
}
if (current.right !== null) {
queue.push(current.right);
}
this.bfsHelper(queue);
}
}
}