Trees Notes

Tree

A nonlinear data structure in Java organized hierarchically with nodes and edges connecting them.

Node

Elements stored in a tree, can be parents, children, leaves, or internal nodes.

Edge

Connects nodes in a tree structure.

Parent

Nodes above another node that connect to a node beneath them.

Child

A node below another node in a tree connected by an edge.

Root

A node with no parents, at the top of the tree.

Leaf

A node with no children, at the bottom of the tree.

Internal Node

A node with both parents and children.

Siblings

Nodes with the same parent in a tree.

Path

Route from a parent node to a leaf in a tree.

Height

Longest path from the root to a leaf in a tree.

Order

Number of children a node can have in a tree.

Balanced Tree

All leaves are within one level of each other.

Complete Tree

Balanced tree where all leaves on the bottom level are on the far-left side.

Preorder Traversal

Visit root, left node, then right node and their children in a tree.

Inorder Traversal

Visit far-left leaf, then parent, and right children in a tree.

Postorder Traversal

Visit children before the root in a tree.

Level-Order Traversal

Visit each level left to right in a tree.

Binary Tree ADT

Abstract Data Type with methods like getRoot, isEmpty, size, contains, and toString for a binary tree.

Ancestor

A node above another node on a path

Binary Tree

A tree where each parent has at most two children

Binary Search Tree

A tree in which the left child is always less than the parent and the right child is always more than the parent

Descendant

A node below another node on a path.

Full

A tree where all nodes have all the children they can have and all leaves are on the same level.

Freelist

A list of all available spaces on an array representation of a tree.

General tree

A tree with no limit on the number of children a parent can have

Level