binary tree
A binary tree is a hierarchical data structure in which each node has at most two children, conventionally called the left child and the right child. One node is the root, and every other node descends from it through exactly one path, so the structure branches downward without cycles, like this:
A few measures describe a binary tree’s shape. The depth of a node is its distance from the root, and the height of the tree is the depth of its deepest node. A tree that stays balanced keeps its height near log n for n nodes, which is what lets operations on it run quickly.
Common varieties include the binary search tree, which orders nodes so that a lookup can discard half the remaining nodes at each step, and the heap, which keeps the largest or smallest value at the root. Binary trees power tasks from expression parsing to priority queues.
A binary tree is a restricted kind of graph, one that is connected and acyclic. Traversing it is a natural use of recursion, since each subtree is itself a smaller binary tree.
Related Resources
Tutorial
Common Python Data Structures (Guide)
In this tutorial, you'll learn about Python's data structures. You'll look at several implementations of abstract data types and learn which implementations are best for your specific use cases.
For additional information on related topics, take a look at the following resources:
- The Python heapq Module: Using Heaps and Priority Queues (Tutorial)
- How to Do a Binary Search in Python (Tutorial)
- Thinking Recursively in Python (Tutorial)
- Stacks and Queues: Selecting the Ideal Data Structure (Course)
- Recursion in Python: An Introduction (Tutorial)
- Recursion in Python (Course)
- Records and Sets: Selecting the Ideal Data Structure (Course)
- Dictionaries and Arrays: Selecting the Ideal Data Structure (Course)
- Creating a Binary Search in Python (Course)
- Thinking Recursively With Python (Course)
- Recursion in Python: An Introduction (Quiz)
