Binary Trees: Definitions

Activity Description

Content

The notion of a Node from a Linked list allows storing of information in memory at different locations. Also, allowed us to provide flexibility on adding/removing/retrieving information. We will consider this design for the following three structures (Binary Tree, Binary Search Tree, AVL Tree).

Binary Tree

A binary tree is a data structure composed of BNodes, with a root. The root has a left and right subtree, and its root is also a BNode. A BNode has a value, a left, and a right BNode.

Definitions

• Root: is the parent of all the nodes in the tree. It has no parents, and it’s responsible for processing any tree. 

• Left subtree: is composed of the left child of the current root. And is recursively composed of left, and right subtrees.

• Right subtree: is composed of the right child of the current root. And is recursively composed of left, and right subtrees.

• A parent is a node composed of left and right children.

• A parent with one child: is called a parent with one dependency (either left/right)

• A leaf is a node that has no children 

• The height of a tree is the largest path from the root to all the leaves.

  • What is the height of a tree that only has one node: 0

  • What is the height of a tree that only has two nodes: 1

  • What is the possible smallest height of a tree that has 3 nodes: 1

  • What is the possible largest height of a tree that has 3 nodes: 2

  • What is the height of an empty tree: -1

Related Videos

Useful Files