May 2017
Intermediate to advanced
310 pages
8h 5m
English
Content preview from Python Data Structures and Algorithms
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
Binary trees
A binary tree is one in which each node has a maximum of two children. Binary trees are very common and we shall use them to build up a BST implementation in Python.
The following figure is an example of a binary tree with 5 being the root node:
Each child is identified as being the right or left child of its parent. Since the parent node is also a node by itself, each node will hold a reference to a right and left node even if the nodes do not exist.
A regular binary tree has no rules as to how elements are arranged in the tree. It only satisfies the condition that each node should have a maximum of two children.