DSA - Trees Flashcards
What is a Tree?
- Very Flexible and powerful data structure
- Involves connect NODES like LL
- Has a Hierarchal structure unlike linear structure of LL
Define Root:
-Node that has no incoming edges (HAS NO PARENTS)
- Unique node at the base of the tree (TOP)
Give 4 example of Types of Trees
- Unary Tree ==> (0-1 Children) ≈ LL
- Binary Tree ==> (0-2 Children)
- Ternary Tree ==> (0-3 Children)
- Quad Tree ==> (0-4 Children)
Define Leaf:
-Node that has no outgoing edges (HAS NO CHILD NODES)
Define Height:
-Length of longest path from root to leaf
LEVEL ≡ HEIGHT
STARTS AT 0
Define Size:
No. of Nodes
Define Edge:
The Link that connects nodes
What is Height & Size of tree with 1 node?
Height = 0
Size = 1
What is Height & Size of tree with no node?
Height = -1
Size = 0
AKA EMPTY TREE
Name the 3 Tree Implementation Options :
- BASIC
- Sibling List
- Array
Explain Basic implementation?
A Doubly Linked List that has a field value and right and left child pointer
- Prev Pointer points to left child
- Next Pointer points to right child
Explain Sibling list Implementation?
Similar to basic in that it is a Doubly Linked List however, the Prev pointer points to left child and the Next pointer point to the sibling of the left child
(This node should be right child of the parent)
Explain Array Implementation?
Binary Trees
Binary Trees use this Array layout where index 1 is the root and the children of node at index i is 2i & (2i)+1
example:
[X|33|10|30|X|X|21|1|X|X|X|X]
33 is root
10 & 30 are 33’s Children
21 & 1 are 30’s Children
Define Binary Tree ADT
Each Parent has only 2 Child Nodes
What does constructor EmptyTree()?
Returns an empty tree
What does constructor MakeTree(V,L,r)?
Returns a new tree, where root node has value V, left subtree l & right subtree r
What does the accessor isEmpty(t)?
Returns tree if list is empty, otherwise False
What does root(t) do?
Returns the root node value of the tree
What does left(t) do?
Returns the left subtree of the tree
What does right(t) do?
Returns the right subtree of the tree
CODE to Create a Tree?
MakeTree(33,
leaf(10),
MakeTree(30,
MakeTree(21,
EmptyTree,
Leaf(25))),
Leaf(1)))
CODE to Reverse a Tree Order?
reverseTree(t) {
if( isEmpty(t)
return (t)
else
return (MakeTree(root(t)),
reverseTree(right(t))
reverseTree(left(t))
}
What does FLATTEN do to the Tree?
Turns the tree into a list (maybe Linked List)
Usually Starting with Left subtree, Root , Right subtree
CODE to Flatten?
flatten(t) {
if Tree.isEmpty(t)
return EmptyList
else
return append(flatten(left(t)),
MakeTree(root(t), flatten(right(t)))))
}