1/59
Vocabulary practice flashcards covering tree terminologies, binary tree types and properties, tree representations, traversals, binary search trees (BST), and graph concepts.
Tree
A nonlinear data structure requiring a two-dimensional representation to organize hierarchical relationships among objects. Formally, it is a finite set of one or more nodes with a specially designated root node, whose remaining nodes are partitioned into n≥0 disjoint sets T1,…,Tn, each of which is itself a tree called a subtree.
Root Node
The origin and first specially designated node in a tree data structure that has no parent. In any tree, there must be exactly one root node.
Leaf Node (Terminal / External Node)
A node in a tree that does not have any children (a node without any successor). Its degree is 0.
Internal Node (Non-terminal Node)
Any non-leaf node in a tree that has at least one child node.
Edge (Link)
A connecting line or pointer drawn from a node to its successor. In any tree with N nodes, there are exactly N−1 edges.
Parent
The immediate predecessor node of another node; a node that has one or more children.
Child Node
An immediate successor or descendant of a node in a tree.
Sibling Nodes
Nodes in a tree that share the exact same parent node.
Degree of a Node
The total number of children belonging to a given node.
Degree of a Tree
The maximum degree among all nodes present within a given tree.
Level
The rank in the tree hierarchy where each step from top to bottom is incremented by one. The level count starts with 0 at the root node.
Depth of a Node
The total number of edges along the path from the root node to that specific node.
Depth of a Tree
The total number of edges from the root node to a leaf node along the longest path.
Height of a Node
The total number of edges from the longest leaf node in its subtree up to that specific node.
Height of a Tree
The total number of edges from the leaf node on the longest path up to the root node (or the maximum number of nodes on a path from root to leaf).
Path
A sequence of consecutive nodes and edges connecting two nodes in a tree or graph.
Length of a Path
The total number of edges contained within a given path.
Ancestor
Any node situated along the path from the root node to a given node. The immediate ancestor is called the parent.
Descendant
Any node situated on a path from a given node down to a leaf node. The immediate descendant is called a child.
Subtree
A portion of a tree that is itself a tree, formed by taking a child of a node along with all of its descendants.
Left Child Right Sibling Representation
A fixed-size node representation of a general tree that uses two pointer fields per node: one pointing to its leftmost child (Left_child) and one pointing to its immediate right sibling (Right_Sibling).
Degree 2 Tree Representation
A binary tree transformation obtained by taking a Left Child-Right Sibling tree and rotating the right sibling pointers clockwise by 45∘.
Binary Tree
A finite set of nodes that is either empty or consists of a root node and two disjoint binary trees called the left subtree and the right subtree, such that every node has at most 2 children.
Full / Strictly Binary Tree
A binary tree where every node other than the leaves has exactly two children (or a binary tree containing the maximum possible number of nodes at all levels).
Complete Binary Tree
A binary tree in which every level, except possibly the last level, is completely filled, and all nodes in the last level appear as far to the left side as possible.
Skewed Binary Tree
A binary tree with n nodes whose height equals n, meaning every internal node has only one child so that all nodes lean exclusively to the left (Left Skewed) or exclusively to the right (Right Skewed).
Array Representation of a Binary Tree
A sequential representation that stores binary tree nodes level-by-level in a 1-D array starting with the root at index 1. For any node at index i, its parent is at ⌊2i⌋ (for i=1), its left child is at 2i, and its right child is at 2i+1.
Linked Representation of a Binary Tree
A dynamic pointer-based representation where each node contains three fields: a data field and two pointer fields pointing to the left child (Left_child) and the right child (Right_child).
Binary Tree Maximum Nodes per Level Property
A property stating that the maximum number of nodes on level i of a binary tree is 2i, where i≥0.
Binary Tree Maximum Nodes Property
A property stating that the maximum number of nodes possible in a binary tree of height h (with root height 0) is 2h+1−1.
Leaf to Degree-2 Nodes Property
A property stating that for any non-empty binary tree T, if n0 is the number of leaf nodes and n2 is the number of nodes of degree 2, then n0=n2+1.
Tree Traversal
The process of visiting each node in a tree exactly once.
Inorder Traversal
A binary tree traversal algorithm where nodes are visited in the order: Left Subtree → Root → Right Subtree.
Preorder Traversal
A binary tree traversal algorithm where nodes are visited in the order: Root → Left Subtree → Right Subtree.
Postorder Traversal
A binary tree traversal algorithm where nodes are visited in the order: Left Subtree → Right Subtree → Root.
Expression Tree
A binary tree representing an algebraic expression where operators appear as internal nodes and operands appear as leaf nodes; its inorder, preorder, and postorder traversals yield infix, prefix, and postfix expressions respectively.
m-ary Tree
A rooted tree in which every internal node has no more than m children. It is called a full m-ary tree if every internal node has exactly m children.
Binary Search Tree (BST)
A binary tree that is either empty or in which every node has a distinct key such that keys in the left subtree are smaller than the node's key, keys in the right subtree are larger (or equal), and both subtrees are themselves binary search trees.
BST Inorder Traversal Property
The property that an inorder traversal of a Binary Search Tree produces all elements in ascending, sorted order.
BST Search Complexity
The time complexity required to search, insert, or delete an item in a binary search tree, which is O(h) where h is the height of the tree (or O(log2(n)) on average).
Inorder Successor
The node with the next highest key value in a binary search tree, found by locating the smallest (leftmost) node in the right subtree of a given node.
BST Deletion with Two Children
A deletion case where the target node has two children and is replaced by its inorder successor (or predecessor), copying that successor's data into the target node and deleting the successor from the subtree.
Graph
A non-linear data structure denoted G=(V,E) consisting of a set of vertices V (nodes) and a set of edges E (lines connecting pairs of vertices) that describe relationships among elements without enforcing a hierarchical structure.
Loop (Graph)
An edge in a graph that connects a vertex directly to itself.
Adjacent Vertices
Two vertices connected directly by an edge. When an edge (x,y) exists, x is adjacent to y, and y is adjacent from x.
Degree of a Vertex
The total number of edges incident to or containing that vertex, denoted deg(x).
Complete Graph
A graph in which every vertex is directly connected by an edge to every other vertex.
Connected Graph (Undirected)
An undirected graph in which there is a path between every pair of vertices.
Strongly Connected Graph
A directed graph in which there exists a directed path from every vertex to every other vertex.
Weakly Connected Graph
A directed graph where a path exists between any two vertices when edge directions are ignored (the underlying undirected graph is connected).
Cycle
A closed path in a graph that begins and ends at the exact same vertex.
Acyclic Graph
A graph that does not contain any cycles.
Weighted Graph
A graph in which each edge is assigned an explicit numerical weight or cost.
Adjacency Matrix
A two-dimensional n×n sequential matrix representation of a graph with n vertices, where entry A[i][j]=1 if an edge exists from vertex vi to vertex vj, and 0 otherwise.
Adjacency List
A linked representation of a graph where a 1-D array of linked lists L stores lists for each node, such that L[i] lists all vertices adjacent from node i.
Incidence Matrix
A two-dimensional matrix of dimension V×E representing a graph, where entry I[i][j]=1 if vertex vi is incident on edge ej, and 0 otherwise.
Edge List (Set Representation)
A straightforward graph representation maintaining two sets: the set of vertices V and the set of edges E (a subset of V×V in sorted pair form).
Depth-First Search (DFS)
A graph traversal algorithm that explores as deeply as possible along each branch before backtracking, implemented efficiently using a stack data structure.
Breadth-First Search (BFS)
A graph traversal algorithm that visits all neighbor nodes at the current depth level before proceeding to deeper levels, implemented efficiently using a queue data structure.
Traversal Node States
The three execution states of a graph node during DFS or BFS: Ready state (STATUS=1, initial state), Waiting state (STATUS=2, placed on stack/queue), and Processed state (STATUS=3, processing completed).