Finding the Predecessor and Successor Node of a Binary Search Tr
- 时间:2020-09-07 12:03:44
- 分类:网络文摘
- 阅读:100 次
A Binary Search Tree (BST) is a commonly used data structure that can be used to search an item in O(LogN) time. A BST should have the following characteristics: its left nodes are smaller than the root and its right nodes are larger than the root.
If we perform an inorder traversal: left nodes first, current node, and then right nodes – we will have a fully sorted sequence.

inorder-traversal-of-a-bst
To find the Predecessor or Sucessor Node of a BST – we can perform the following algorithms:

predecessor-and-successor-of-a-bst
Find the Predecessor Node of a Binary Search Tree
The predecessor node is the largest node that is smaller than the root (current node) – thus it is on the left branch of the Binary Search Tree, and the rightmost leaf (largest on the left branch).
The C++ function to find the predecessor node of a BST node:
1 2 3 4 5 6 | TreeNode* predecessor(TreeNode* root) { if (!root) return nullptr; root = root->left; while (root->right) root = root->right; return root; } |
TreeNode* predecessor(TreeNode* root) { if (!root) return nullptr; root = root->left; while (root->right) root = root->right; return root; }
And below is the Java implementation to get the predecessor node of a Binary Search Tree:
1 2 3 4 5 6 | public int predecessor(TreeNode root) { if (root == null) return null; root = root.left; while (root.right != null) root = root.right; return root; } |
public int predecessor(TreeNode root) { if (root == null) return null; root = root.left; while (root.right != null) root = root.right; return root; }
Python function to get the predecessor of a BST:
1 2 3 4 5 6 7 | def predecessor(root): if root is None: return None root = root.left while root.right: root = root.right return root |
def predecessor(root): if root is None: return None root = root.left while root.right: root = root.right return root
Find the Successor Node of a Binary Search Tree
On the other hand, the successor node is the smallest node that is bigger than the root/current – thus it is on the right branch of the BST, and also on the leftmost leaf (smallest on the right branch).
The C++ function to get the successor node of a Binary Search Tree.
1 2 3 4 5 6 | TreeNode* successor(TreeNode* root) { if (!root) return nullptr; root = root->right; while (root->left) root = root->left; return root; } |
TreeNode* successor(TreeNode* root) { if (!root) return nullptr; root = root->right; while (root->left) root = root->left; return root; }
Java method to get the successor:
1 2 3 4 5 6 | public int successor(TreeNode root) { if (root == null) return null; root = root.right; while (root.left != null) root = root.left; return root; } |
public int successor(TreeNode root) { if (root == null) return null; root = root.right; while (root.left != null) root = root.left; return root; }
Finally, the below is the Python implementation of getting a sucessor node of a BST:
1 2 3 4 5 6 7 | def successor(root): if root is None: return None root = root.right while root.left: root = root.left return root |
def successor(root): if root is None: return None root = root.right while root.left: root = root.left return root
All implementation of finding successor or predecessor takes O(1) constant space and run O(N) time (when BST is just a degraded linked list) – however, on average, the complexity is O(LogN) where the binary tree is balanced.
Finding successor or predecessor is very useful – for example, we can use this to delete a node in a binary search tree.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:齐桓公伐楚盟屈完原文及翻译 曹刿论战原文及翻译 数学题:组成只能被3整除不能被9整除的4位数 数学题:将某款服装按标价打8折出售,仍可盈利10% 数学题:把一根长30cm,底面半径是8cm的圆木平均锯成4段 数学题:甲乙两种皮鞋的原价相同,换季时 奥数题:1994年“世界杯”足球赛中 数学题:如何按照一定的比例把小长方形扩大成与大长方形完全重的图形 问答题:说明学生总数、每辆车载客数、客车数成什么比例 数学题:有一个礼品盒,用彩绳扎成如右图的形状
- 评论列表
-
- 添加评论