Binary tree is a tree where each node has at most two children.
The two children are usually called:
- Left child
- Right child
Binary trees are useful for representing hierarchical decisions, sorted data, expressions, and tree-shaped algorithms.
Common traversals:
- Preorder: visit the node, then left subtree, then right subtree
- Inorder: visit the left subtree, then node, then right subtree
- Postorder: visit the left subtree, then right subtree, then node
- Level order: visit nodes level by level
Binary trees are the base idea behind more specialized structures such as binary search trees and heaps.
flowchart TD Root["root"] --> Left["left child"] Root --> Right["right child"] Left --> LL["left subtree"] Left --> LR["right subtree"]
Anki
id: binary-tree-definition deck: Computer Science::Data Structures tags: data-structures tree binary-tree
Q: How many children can a node have in a binary tree? A: At most two: usually called the left child and right child.
id: binary-tree-inorder-traversal deck: Computer Science::Data Structures tags: data-structures tree binary-tree traversal
Q: In a binary search tree, why is inorder traversal useful? A: It visits the values in sorted order.