The stack is a data structure whose purpose is to enforce the order of first-in-last-out (FILO), alternatively, you can visualize this order as last-in-first-out (LIFO). In previous sections, we discussed this data structure indirectly through recursion. If you remember the following error:
StackOverflowError
It was probably because the base case was not well-defined, or the recursive case kept
*Missing 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).
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