Data Structures and Algorithms in Java

Flashcards about Trees, Binary Trees, and Binary Search Trees

What is a Tree in computer science?

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

What is the Root of a tree?

Unique node without a parent.

What is an Internal node?

Node with at least one child.

What is an External (leaf) node?

Node without children.

What are Ancestors of a node?

Parent, grandparent, great-grandparent, etc.

What are Descendants of a node?

Child, grandchild, great-grandchild, etc.

What is the Level of a node?

The level of the root is 1. If a father has level i then its children has level i+1.

What is the Height of a tree?

Maximum level in a tree. A single node is a tree of height 1. The height of an empty tree is 0.

What is the Degree (order) of a node?

Number of its non-empty children.

What is a Path in a tree?

Each node has to be reachable from the root through a unique sequence of arcs (edges).

What is Tree traversal?

Visiting each node in the tree exactly one time.

What happens during a Pre-order Traversal?

Visit a node before its descendants.

What happens during a Postorder Traversal?

Visit a node after its descendants.

What happens during a Breadth-first Traversal?

Visit a node first, then all its children, then all its grandchildren,…

What is a Binary tree?

A tree in which each node has at most two children.

What is a Proper binary tree?

Every node other than the leaves has two children.

What is a Complete Binary Tree?

All non-terminal nodes have both their children, and all leaves are at the same level.

What is Breadth-first traversal?

Visiting each node starting from the lowest (or highest) level and moving down (or up) level by level, visiting nodes on each level from left to right (or from right to left)

What is Pre-order (NLR)?

Node, Left, Right

What is In-order (LNR)?

Left, Node, Right

What is Post-order (LRN)?

Left, Right, Node

Inorder sequence example

D B E A F C

Preorder sequence example

A B D E C F

How can Binary trees be implemented?

Implemented as arrays or as linked structures.

What are the properties of a Binary Search Tree (BST)?

The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

What are the three cases of deleting a node from the binary search tree?

The node is a leaf; it has no children. The node has one child. The node has two children.

What is Deleting by merging?

Making one tree out of the two subtrees of the node and then attaching it to the node’s parent

What is Deletion by Copying?

Replace the key being deleted with its immediate predecessor (or successor)