Algorithms Flashcards
In which data structure a Traversal usually happen?
A tree
What’s a node in the Tree data structure?
A node is a structure which may contain a value or condition, or represent a separate data structure.
What’s a Root in the Tree data structure?
The top node in a tree, the prime ancestor.
What’s a child in the Tree data structure?
A node directly connected to another node moving away from the root, an immediate descendant.
What’s a parent in the Tree data structure?
The inverse of a child, an immediate ancestor.
What is a leaf in the Tree data structure?
A node with no children
What is an Internal node in the Tree data structure?
A node with at least one child.
What is an edge in the Tree data structure?
The connection between one node and another
What is depth in the Tree data structure?
The distance between a node and the root
What is a level in the Tree data structure?
The number of edges between a node and the root + 1
What is the height of the Tree data structure?
The number of edges on the longest path between a node and a descendant leaf.
What is a breadth in the Tree data structure?
Is the number of leaves.
What is a subtree in the Tree data structure?
A tree T is a tree consisting of a node in T and all of its descendants in T.
What is a binary tree?
Is a tree data structure in which each node has at most two children, which are referred to as the left and right child.
What is a binary search tree? List 3 main properties of a binary search;
is a special type of binary tree which has the following properties.
The left subtree of a node contains only nodes with keys lesser than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. The left and right subtree each must also be a binary search tree.
What is a tree traversal?
In computer science, tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.
What are the two main Tree Traversal algorithms?
Depth-First Search(DFS) and Breadth-First Search(BFS)
What are the two main Tree Traversal algorithms?
Depth-First Search(DFS) and Breadth-First Search(BFS)
How does the Depth-First Search(DFS) algorithm work?
t starts with the root node and first visits all nodes of one branch as deep as possible of the chosen Node and before backtracking, it visits all other branches in a similar fashion.
How does the Breadth-First search (BFS) algorithm work?
It also starts from the root node and visits all nodes of current depth before moving to the next depth in the tree.
What are the three main Depth-First Search(DFS) algorithms variants?
Preorder Traversal (current-left-right)— Visit the current node before visiting any nodes inside left or right subtrees.
Inorder Traversal (left-current-right)— Visit the current node after visiting all nodes inside left subtree but before visiting any node within the right subtree.
Postorder Traversal (left-right-current) — Visit the current node after visiting all the nodes of left and right subtrees.
