A byte-sized article that can teach or remind you of a programming concept and/or language in <2 minutes.
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)
Hope you learned something new from this article 🙏!
If you have any comments, please leave them below. You can always DM and ask me anything on Twitter (@phuctm97) 😉
Top comments (0)