Binary Search Trees

These flashcards cover essential vocabulary and concepts related to binary search trees (BSTs), their structure, operations, and properties.

Binary Search Tree (BST)

A binary tree where each node's left subtree contains keys less than the node's key and the right subtree contains keys greater than the node's key.

Node

An element that stores information in a binary tree, consisting of a key value and potentially other data.

Left Subtree

The subtree that contains nodes with keys less than the parent node's key.

Right Subtree

The subtree that contains nodes with keys greater than the parent node's key.

Inorder Traversal

A method of tree traversal that visits the left subtree, the current node, and then the right subtree, displaying nodes in ascending order.

Preorder Traversal

A method of tree traversal that visits the current node first, followed by the left subtree and then the right subtree.

Postorder Traversal

A method of tree traversal that visits the left subtree first, then the right subtree, and finally the current node.

Height of Tree

The longest path from the root node to a leaf node.

Efficient Operations

Key operations that can be performed efficiently in a BST including insertion, searching, deletion, and sorted printing.

Duplicate Keys

In the context of a BST, keys which are allowed to be equal; in this case, duplicates can either go into the left or right subtree depending on the implementation.

TreeNode

A class that represents a node in a binary tree, containing an element and references to left and right child nodes.

Binary Tree Representation

Utilizes a structure of linked nodes where each node has a value and pointers to its left and right children.

Delete Operation

A process to remove a specified element from a BST, which involves finding the node and its parent, and then adjusting the tree structure accordingly.

Searching an Element

The process of locating a node with a specific key value in the BST, beginning from the root and moving to left or right children based on comparison.

AbstractTree Class

A class that partially implements the Tree interface for common operations in tree structures.

Tree Interface

Defines common operations for trees, such as searching, inserting, deleting, and traversing.

Time Complexity

The amount of time taken to perform operations based on the size of the input, represented in terms of Big O notation, e.g., O(n) for traversals.

Rightmost Node

The node that contains the largest key in the left subtree of a targeted node, crucial in the deletion operation.

Binary Tree Traversal

The method of visiting all nodes in a tree data structure exactly once for processing or displaying their values.