Data Structures: Trees and Binary Trees

These flashcards cover key vocabulary terms and definitions related to trees and binary trees in data structures.

Tree

A collection of data items related to each other according to a specific hierarchical structure.

Node

Each item in the tree.

Root Node

The node at the top of the tree.

Edges

Lines or paths connecting nodes.

Leaf Node

A node that has a degree of 0.

Internal Nodes

Nodes that have a degree greater than 0.

Subtree

A tree within a tree.

Sibling

Nodes with the same parent node.

Grandparent

The parent of a parent node.

Ancestors

Parent nodes, grandparent nodes, and so on.

Levels

Position of a node relative to the root.

Degree of a Node

The number of subtrees of a node.

Degree of a Tree

The degree of the node with the highest degree.

Depth of the Node

The number of edges from the root to the node.

Depth of the Tree

The number of edges from the root to the deepest leaf node.

Height of the Node

The number of edges from the node to its deepest leaf node.

Height of the Tree

The height of the root node.

Binary Tree

A tree in which every node can have at most two children.

Binary Search Tree

An ordered binary tree where all elements in the left subtree are less than the root and all in the right subtree are greater.

Binary Expression Tree

A binary tree used to represent arithmetic expressions with operators and operands.

Pre-order Traversal

Tree traversal method used to get prefix expression and create a copy of the tree.

In-order Traversal

Tree traversal method used to get infix expression of an expression tree.

Post-order Traversal

Tree traversal method used to get postfix expression and delete the tree.

Leaf Node Deletion

Simply remove/disconnect the leaf node to be deleted from the tree.

In-order Successor

The least value element in the right subtree of the deleting node.

In-order Predecessor

The greatest value element in the left subtree of the deleting node.

Balanced Tree

A binary search tree with equal items on each subtree to minimize the maximum path to any leaf.

Height-Balanced

A binary search tree where the left and right subtree heights of each node are within 1.