Hierarchical structures; binary search trees keep ordered data.
A tree is a hierarchy of nodes with a root, children and leaves. Binary trees have at most two children; binary search trees keep left<node<right so search is O(h). Traversals: in-order, pre-order, post-order, level-order. Used for file systems, parsing and indexes.
In-order traversal of a BST visits keys in sorted order.
Trees organise hierarchical data and ordered sets, which underpins file systems, databases and parsers.
Hierarchical structures; binary search trees keep ordered data.
Trees organise hierarchical data and ordered sets, which underpins file systems, databases and parsers.
A tree where each node's left subtree holds smaller values and the right holds larger values, which allows fast search when the tree is balanced.
The tree becomes a long chain, and operations slow to linear time, which is why balanced trees are used.
Typical applications include representing the folder structure of a project, storing ordered records in a binary search tree for range queries and modelling the syntax of an arithmetic expression.
Study "Hash tables" first (topic 21 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Height and depth. Degenerate trees become lists. Tries for prefixes.
In-order traversal of a BST visits keys in sorted order.
The next topic is "Balanced trees", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 22 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.