Python Binary Search Tree: Find the kth smallest element in a given a binary search tree (BST)
Python Binary Search Tree: Exercise-6 with Solution
Write a Python program to find the kth smallest element in a given binary search tree.
Sample Solution:
Python Code:
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def kth_smallest(root, k):
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
break
root = root.right
return root.val
root = TreeNode(8)
root.left = TreeNode(5)
root.right = TreeNode(14)
root.left.left = TreeNode(4)
root.left.right = TreeNode(6)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.right = TreeNode(24)
root.right.right.left = TreeNode(22)
print(kth_smallest(root, 2))
print(kth_smallest(root, 3))
Sample Output:
5 8
Flowchart:

Python Code Editor:
Contribute your code and comments through Disqus.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
Python: Tips of the Day
Joining Collection:
name = ["Owen", "Eddie"] print(" ".join(name))
Owen Eddie
- Weekly Trends
- Python Interview Questions and Answers: Comprehensive Guide
- Scala Exercises, Practice, Solution
- Kotlin Exercises practice with solution
- MongoDB Exercises, Practice, Solution
- SQL Exercises, Practice, Solution - JOINS
- Java Basic Programming Exercises
- SQL Subqueries
- Adventureworks Database Exercises
- C# Sharp Basic Exercises
- SQL COUNT() with distinct
- JavaScript String Exercises
- JavaScript HTML Form Validation
- Java Collection Exercises
- SQL COUNT() function
- SQL Inner Join
We are closing our Disqus commenting system for some maintenanace issues. You may write to us at reach[at]yahoo[dot]com or visit us at Facebook