Binary tree

Programming basics

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Image of a tree

tree vocabulary

In addition to NORMAL tree vocabulary:

• root node
• parent node
• child node
• leaf node

Binary Trees have special vocabulary:

• left-child
• right-child
• subtree

Practical applications of a tree

• Trees can be used to store data that has an inherent hierarchical structure. For example, an operating system may use a tree for directories, files and folders in its file management system.
• They are dynamic, which means that it is easy to add and delete nodes.
• They are easy to search and sort using standard traversal algorithms.
• They can be used to process the syntax of statements in natural and programming languages so are commonly used when compiling programming code.

Binary Tree - video example

This video provides a basic introduction to binary trees.

Traversal

Traversal describes the order in which nodes are visited.

I used this image with great gratitude from the guys at Dartford Grammar School

Standards

• Describe how trees operate logically (both binary and non-binary).
• Define the terms: parent, left-child, right-child, subtree, root and leaf.
• State the result of inorder, postorder and preorder tree traversal.
• Sketch binary trees.

See Also

• Abstract data structures
• tree

External Links

high level discussion of binary trees

Give a detailed account or picture of a situation, event, pattern or process.

Give the precise meaning of a word, phrase, concept or physical quantity.

Give a specific name, value or other brief answer without explanation or calculation.

Give a specific name, value or other brief answer without explanation or calculation.

Represent by means of a diagram or graph (labelled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features.