Computer science

· Binary Tree

Data Associations look like a tree

A node orientation that has A Parent/Root and Left / Right relationship

· Describe the Node structure for Binary Tree

· Root / Root Node

Node that is the beginning of the tree

· Path/Edge

· Parent

A node that has nodes associated with it.

Left and Right Node

· Children

Nodes connected to a parent node

· Leaf

Online Resource 1 , 2 , 3

· Binary Search Tree

Tree Structure where the nodes are “Sorted” or “Inserted” in a particular relationship to the previous node.

Traverse → Access all THE NODES

Inorder

Post Order

https://algorithmtutor.com/Data-Structures/Tree/Binary-Search-Trees/

· Right Child

HAs a greater value than the Parent or root Node

· Left Child

Has a lesser value than the Parent or root Node

· Difference between Binary Tree and Binary Search Tree

Binary Tree	Binary Search Tree
Binary Tree is a specialized form of tree which represents hierarchical data in a tree structure.	Binary Search Tree is a type of binary tree which keeps the keys in a sorted order for fast lookup.
Each node must have at the most two child nodes with each node being connected from exactly one other node by a directed edge.	The value of the nodes in the left subtree are less than or equal to the value of the root node, and the nodes to the right subtree have values greater than or equal to the value of the root node.
There is no relative order to how the nodes should be organized.	It follows a definitive order to how the nodes should be organized in a tree.
It’s basically a hierarchical data structure that is a collection of elements called nodes.	It’s a variant of the binary tree in which the nodes are arranged in a relative order.
It is used for fast and efficient lookup of data and information in a tree structure.	It is mainly used for insertion, deletion, and searching of elements.

· Why does the Binary Tree / Binary Search Tree implementation improve the Linked List?

◆ Binary search tree can cut in half each node, just like binary search

◆ Linked list are more like linear search where you have to traversal each element on by one

How is recursion utilized to traverse a Binary Search Tree?

● Recursion - function can call itself to repeat code block

● Similar to a loop

TIME COMPLEXITY ANALYSIS

Efficiency of the algorithm

Stack - LIFO

Queue - FIFO

Map or Tree

Doubly Linked List Node next* previous*	WORST CASE	AVERAGE CASE	BEST CASE
Insert “Head”	O(n)		O(1) - Queue
Insert “Tail”	O(n)		O(1) - Stack / Queue
Delete “Head”	O(n)		O(1) - Queue
Delete “Tail”	O(n)		O(1) - Stack
Search	O(n)		O(1)
Linked List Traversal	O(n)

Trade - Off for the map

Bad → Takes more Memory because need an over sized array to avoid collision |

We gain Search Speed → In map we get almost O(1) for any element Structure

Hash Map	WORST CASE	AVERAGE CASE	BEST CASE
Insertion	O(n)		O(1) Hopefully O(log n)
Deletion	O(n)		O(1) Hopefully O(log n)
Search	O(n)		O(1) Hopefully O(log n)

Linked List allows for Better Dynamic Allocation. No size Limit the linked lists. Ours can add and remove nodes to have constant alignment between data and its storage RAM.

Nodes are placed HEAP

Doubly List → Linear Data Structure + No Indices

Binary Search Tree Node left* → Nodes with lesses value are placed on the left right* → Nodes with greeted value are placed on the right	WORST CASE	AVERAGE CASE	BEST CASE
Insertion	O(n)		O(log n) O(1)
Deletion	O(n)		O(log n) O(1)
Search	O(n)		O(log n) O(1)

MEMORY ALLOCATION ANALYSIS

Linked List (Doubly / Singly) O(n)

Hash Map O(n^2) or (n^3)

Binary Search Tree O(n)

· Please compare the Trade-Offs Associated with implementing Binary Search Tree v Hash Map?

Analyze Legacy Code of Hash Map w/ Collisions resolved w/ Embedded Linked Lists

A
B
C
D
E
F
G
H
I
J
K
L
M
N