Trees, Binary Search Trees, and Graphs

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/59

flashcard set

Earn XP

Description and Tags

Vocabulary practice flashcards covering tree terminologies, binary tree types and properties, tree representations, traversals, binary search trees (BST), and graph concepts.

60 Terms

1
New cards

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≥0n \ge 0 disjoint sets T1,…,TnT_1, \dots, T_n, each of which is itself a tree called a subtree.

2
New cards

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.

3
New cards

Leaf Node (Terminal / External Node)

A node in a tree that does not have any children (a node without any successor). Its degree is 00.

4
New cards

Internal Node (Non-terminal Node)

Any non-leaf node in a tree that has at least one child node.

5
New cards

Edge (Link)

A connecting line or pointer drawn from a node to its successor. In any tree with NN nodes, there are exactly N−1N - 1 edges.

6
New cards

Parent

The immediate predecessor node of another node; a node that has one or more children.

7
New cards

Child Node

An immediate successor or descendant of a node in a tree.

8
New cards

Sibling Nodes

Nodes in a tree that share the exact same parent node.

9
New cards

Degree of a Node

The total number of children belonging to a given node.

10
New cards

Degree of a Tree

The maximum degree among all nodes present within a given tree.

11
New cards

Level

The rank in the tree hierarchy where each step from top to bottom is incremented by one. The level count starts with 00 at the root node.

12
New cards

Depth of a Node

The total number of edges along the path from the root node to that specific node.

13
New cards

Depth of a Tree

The total number of edges from the root node to a leaf node along the longest path.

14
New cards

Height of a Node

The total number of edges from the longest leaf node in its subtree up to that specific node.

15
New cards

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).

16
New cards

Path

A sequence of consecutive nodes and edges connecting two nodes in a tree or graph.

17
New cards

Length of a Path

The total number of edges contained within a given path.

18
New cards

Ancestor

Any node situated along the path from the root node to a given node. The immediate ancestor is called the parent.

19
New cards

Descendant

Any node situated on a path from a given node down to a leaf node. The immediate descendant is called a child.

20
New cards

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.

21
New cards

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).

22
New cards

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∘45^\circ.

23
New cards

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 22 children.

24
New cards

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).

25
New cards

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.

26
New cards

Skewed Binary Tree

A binary tree with nn nodes whose height equals nn, 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).

27
New cards

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 11. For any node at index ii, its parent is at ⌊i2⌋\lfloor \frac{i}{2} \rfloor (for i≠1i \ne 1), its left child is at 2i2i, and its right child is at 2i+12i + 1.

28
New cards

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).

29
New cards

Binary Tree Maximum Nodes per Level Property

A property stating that the maximum number of nodes on level ii of a binary tree is 2i2^i, where i≥0i \ge 0.

30
New cards

Binary Tree Maximum Nodes Property

A property stating that the maximum number of nodes possible in a binary tree of height hh (with root height 00) is 2h+1−12^{h+1} - 1.

31
New cards

Leaf to Degree-2 Nodes Property

A property stating that for any non-empty binary tree TT, if n0n_0 is the number of leaf nodes and n2n_2 is the number of nodes of degree 2, then n0=n2+1n_0 = n_2 + 1.

32
New cards

Tree Traversal

The process of visiting each node in a tree exactly once.

33
New cards

Inorder Traversal

A binary tree traversal algorithm where nodes are visited in the order: Left Subtree →\rightarrow Root →\rightarrow Right Subtree.

34
New cards

Preorder Traversal

A binary tree traversal algorithm where nodes are visited in the order: Root →\rightarrow Left Subtree →\rightarrow Right Subtree.

35
New cards

Postorder Traversal

A binary tree traversal algorithm where nodes are visited in the order: Left Subtree →\rightarrow Right Subtree →\rightarrow Root.

36
New cards

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.

37
New cards

mm-ary Tree

A rooted tree in which every internal node has no more than mm children. It is called a full mm-ary tree if every internal node has exactly mm children.

38
New cards

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.

39
New cards

BST Inorder Traversal Property

The property that an inorder traversal of a Binary Search Tree produces all elements in ascending, sorted order.

40
New cards

BST Search Complexity

The time complexity required to search, insert, or delete an item in a binary search tree, which is O(h)O(h) where hh is the height of the tree (or O(log⁡2(n))O(\log_2(n)) on average).

41
New cards

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.

42
New cards

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.

43
New cards

Graph

A non-linear data structure denoted G=(V,E)G = (V, E) consisting of a set of vertices VV (nodes) and a set of edges EE (lines connecting pairs of vertices) that describe relationships among elements without enforcing a hierarchical structure.

44
New cards

Loop (Graph)

An edge in a graph that connects a vertex directly to itself.

45
New cards

Adjacent Vertices

Two vertices connected directly by an edge. When an edge (x,y)(x, y) exists, xx is adjacent to yy, and yy is adjacent from xx.

46
New cards

Degree of a Vertex

The total number of edges incident to or containing that vertex, denoted deg(x)\text{deg}(x).

47
New cards

Complete Graph

A graph in which every vertex is directly connected by an edge to every other vertex.

48
New cards

Connected Graph (Undirected)

An undirected graph in which there is a path between every pair of vertices.

49
New cards

Strongly Connected Graph

A directed graph in which there exists a directed path from every vertex to every other vertex.

50
New cards

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).

51
New cards

Cycle

A closed path in a graph that begins and ends at the exact same vertex.

52
New cards

Acyclic Graph

A graph that does not contain any cycles.

53
New cards

Weighted Graph

A graph in which each edge is assigned an explicit numerical weight or cost.

54
New cards

Adjacency Matrix

A two-dimensional n×nn \times n sequential matrix representation of a graph with nn vertices, where entry A[i][j]=1A[i][j] = 1 if an edge exists from vertex viv_i to vertex vjv_j, and 00 otherwise.

55
New cards

Adjacency List

A linked representation of a graph where a 1-D array of linked lists LL stores lists for each node, such that L[i]L[i] lists all vertices adjacent from node ii.

56
New cards

Incidence Matrix

A two-dimensional matrix of dimension V×EV \times E representing a graph, where entry I[i][j]=1I[i][j] = 1 if vertex viv_i is incident on edge eje_j, and 00 otherwise.

57
New cards

Edge List (Set Representation)

A straightforward graph representation maintaining two sets: the set of vertices VV and the set of edges EE (a subset of V×VV \times V in sorted pair form).

58
New cards

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.

59
New cards

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.

60
New cards

Traversal Node States

The three execution states of a graph node during DFS or BFS: Ready state (STATUS=1\text{STATUS} = 1, initial state), Waiting state (STATUS=2\text{STATUS} = 2, placed on stack/queue), and Processed state (STATUS=3\text{STATUS} = 3, processing completed).