Trees and Binary Trees Lecture Notes

This set of vocabulary flashcards covers fundamental tree terminologies, binary tree properties, traversal algorithms, and specialized tree structures based on the lecture notes.

Tree

An abstract model of a hierarchical structure consisting of nodes with a parent-child relation.

Linear Data Structures

Data structures like lists, arrays, queues, and stacks where elements are positioned before and after one another.

Root

The node without a parent that provides the access point to the tree.

Internal node

A node with at least one child.

External node (leaf)

A node without children.

Ancestors of a node

The parent, grandparent, grand-grandparent, and so on, of a node.

Depth of a node

The number of ancestors a node has.

Height of a tree

The maximum depth of any node.

Descendant of a node

The child, grandchild, grand-grandchild, and so on, of a node.

Subtree

A tree consisting of a node and its descendants.

Siblings

Nodes that share the same parent.

Edge

The connection between nodes.

Path

The sequence of nodes followed along edges from the root to a destination node.

Ordered tree

A tree where the children of a node are in a particular order.

Binary Tree

A tree type in which each node can have a maximum of 2 children: a Left child and a Right child.

Minimum height of a binary tree

For a tree of size $n$, the minimum height is calculated as $[ ext{log}_2(n)]$.

Full binary tree

A binary tree where every internal node contains either 0 or 2 children.

Perfect binary tree

A binary tree where all possible nodes are full from top to bottom, and all leaf nodes are on the same level.

Tree Traversal

A systematic manner of visiting the nodes of a tree with a running time of $O(n)$.

Pre-order traversal

A traversal where a node is visited before its descendants, following the left node first.

In-order traversal

A traversal where nodes are read from left to right: first traversing the left subtree, then visiting the node, then following the right subtree.

Post-order traversal

A traversal where a node is visited after its descendants: processing the children first, then the root.

Breadth First Tree Traversal

A traversal where nodes are visited by level (from left to right) using a queue to store child nodes.

Arithmetic Expression Tree

A binary tree where internal nodes store operators and external nodes (leaves) store operands.