Binary Trees and Binary Search Trees
Trees organize data hierarchically: file systems, HTML documents, organization charts, and database indexes are all trees. The binary search tree (BST) adds one ordering rule to a binary tree and suddenly supports search, insert, and delete in O(log n). Everything you learned about recursion pays off here, because trees are recursive objects: every subtree is itself a tree.
What You'll Learn
- Tree vocabulary: root, leaf, height, subtree
- Building a binary tree from Node objects
- The three depth-first traversals, and why in-order visits a BST in sorted order
- BST insert and search in O(log n)
Trees Are Recursive Structures
A binary tree node has a value and up to two children. The same Node idea as linked lists, with left and right instead of next:
Both functions follow the same recursive template: handle the empty tree (base case), recurse into both children, combine. Nearly every tree algorithm looks like this.
The Three Depth-First Traversals
Traversal order is just "when do you visit the node relative to its children":
- Pre-order: node, left, right (copying or serializing a tree)
- In-order: left, node, right (sorted output on a BST)
- Post-order: left, right, node (deleting or sizing a tree bottom-up)
Look at the in-order output: [1, 3, 6, 8, 10, 14], perfectly sorted. That is not a coincidence; the tree above is a BST.
Binary Search Trees
The BST rule: for every node, everything in the left subtree is smaller, everything in the right subtree is larger. Searching then works exactly like binary search: compare and go left or right, discarding half the tree (on average) at each step. Open this one fullscreen and experiment:
The search path for 65 touches only 4 of the 8 nodes. On a balanced tree of a million nodes, that path is about 20 nodes long: O(log n).
The Balance Caveat
Insert already-sorted values into a BST and every node goes right: the "tree" degenerates into a linked list, and operations become O(n). Production systems use self-balancing trees (AVL, red-black) that rotate nodes to stay O(log n); Python's dict avoids the issue entirely by hashing. For interviews, know that the O(log n) claim assumes balance.
Where Trees Meet Real Life
- Your file system is a tree; sizes are computed post-order
- HTML is a tree; renderers walk it pre-order
- Databases index columns with B-trees, a generalization of BSTs
- Autocomplete uses tries, trees keyed by characters
Exercises
Key Takeaways
- Trees are recursive: most algorithms are base case + recurse both sides + combine
- Pre/in/post-order differ only in when the node is visited relative to its children
- In-order traversal of a BST produces sorted values
- BST search and insert are O(log n) when balanced, O(n) when degenerate
- Real systems keep trees balanced (AVL, red-black, B-trees) to protect the O(log n)
اختبار قصير
التالي · الدرس 10 من 11
Graphs, BFS, and DFS
قراءة 2 دقيقة
أنهيت 9 من 11 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

