Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bst
data structures

# What is a Binary Search Tree?

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

A Binary Search Tree is a binary tree where each node contains a key and an optional associated value. It allows particularly fast lookup, addition, and removal of items.

The nodes are arranged in a binary search tree according to the following properties:

• The left subtree of a particular node will always contain nodes with keys less than that node’s key.

• The right subtree of a particular node will always contain nodes with keys greater than that node’s key.

• The left and the right subtree of a particular node will also, in turn, be binary search trees.

## Time Complexity

In average cases, the above mentioned properties enable the insert, search and deletion operations in $O(log n)$ time where n is the number of nodes in the tree. However, the time complexity for these operations is $O(n)$ in the worst case when the tree becomes unbalanced.

## Space Complexity

The space complexity of a binary search tree is $O(n)$ in both the average and the worst cases.

## Types of Traversals

The Binary Search Tree can be traversed in the following ways:

1. Pre-order Traversal
2. In-order Traversal
3. Post-order Traversal

The pre-order traversal will visit nodes in Parent-LeftChild-RightChild order.

The in-order traversal will visit nodes in LeftChild-Parent-RightChild order. In this way, the tree is traversed in an ascending order of keys.

The post-order traversal will visit nodes in LeftChild-RightChild-Parent order.

RELATED TAGS

bst
data structures