Discover published sets by community

A binary search tree is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.

A balanced binary search tree is one where the depth of the two subtrees of every node never differ by more than one. AVL trees and Red-Black trees are examples of balanced BSTs.

Pre-order traversal is a method of traversing a binary search tree where the nodes are visited in a root-left-right order. This traversal is used to create a copy of the tree or to get a prefix expression on an expression tree.

Deleting a node in a BST can be done in three ways: removing a leaf with no children, removing a node with one child, or removing a node with two children. The complexity comes with maintaining the BST properties after deletion.

To insert into a BST, start at the root and compare the keys. Insert the node as a leaf where the current node is null, preserving the BST property that left children are less than their parent and right children are greater.

The successor of a node in a BST is the node with the smallest key greater than the given node. It is found by taking the right child once and then as many left children as possible.

Post-order traversal is a method of traversing a binary search tree where the nodes are visited in a left-right-root order. This traversal is used to delete the tree or to get a postfix expression on an expression tree.