C DSALesson 63Free preview

C Trees

This lesson is part of C · All levels

Summary

A tree is a hierarchical structure of branching nodes, where each node can have left and right children, and a node without children is called a leaf. The binary search tree (BST) ranks the left child with a smaller value and the right child with a larger value than the mother, so the search can throw half the data away at each step. Tree searches are generally written recursively with patterns of inorder, preorder, and postorder.

Key points

The basic terms: root, parent, child, leaf, subtree, depth, and height.
In BST, the left rule is smaller and the right rule is larger, so the inorder traversal produces sequential data.
It's very natural for a tree to be recursive because every child is a subtree with the same structure.
The preorder visits the root first, the inorder visits the root in the middle, and the postorder visits the last root.
A balanced tree gives a search, but if tilted to one side it can be as low as the one.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.