Binary Tree

A binary tree is a hierarchical data structure in which each node holds a value and has at most two children, called the left child and the right child. The top node is the root, and nodes with no children are leaves. Trees are used for file systems, expression parsing and organising data hierarchically.

A binary search tree (BST) keeps every value in a node's left subtree smaller than the node and every value in its right subtree larger, so searching, inserting and deleting take O(log n) time when the tree is balanced. Self-balancing trees, such as AVL and red-black trees, keep it that way. Trees are visited in inorder, preorder, postorder or level order.