w3resource

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:

Flowchart: find the k<sup>th</sup> smallest element in a given a binary search tree.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to convert a given array elements to a height balanced Binary Search Tree (BST).

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.

Python: Tips of the Day

Joining Collection:

name = ["Owen", "Eddie"] 
print(" ".join(name))
Owen Eddie

 





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