# Binary Search Tree And Real-world Applications

Minh-Phuc Tran on Nov 15, 2020

## Definition

A binary search tree (BST) is a binary tree data structure that has

The left subtree of a node contains only nodes with values less than the node's value.

The right subtree of a node contains only nodes with values greater than the node's value.

The left and right subtree each is a binary search tree, too.

*(Image's source: GeeksForGeeks)*

## Real-world Applications

### 3D game engines

Almost every 3D engine uses BST to determine which objects should be rendered in a 3D world, which is basically buffering Z orders instead of recalculating complex 3D positioning on every render.

It's famously used in Doom 1993 as the first time a BST had even been used in a game.

*(Image's source: Wikipedia)*

### Compilers

To efficiently parse syntax expressions (e.g. programming languages), compilers use a special BST called syntax tree.

*(Image's source: Wikipedia)*