In this Leetcode Kth Smallest Element in a BST problem solution you are given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.
Problem solution in Python.
class Solution: def kthSmallest(self, root: TreeNode, k: int) -> int: def inorder(node, arr): if node is None: return arr arr = inorder(node.left, arr) arr.append(node.val) arr = inorder(node.right, arr) return arr arr = inorder(root, []) return arr[k-1]
Problem solution in Java.
class Solution { int count; int res; public int kthSmallest(TreeNode root, int k) { count = k; res = 0; helper(root); return res; } private void helper(TreeNode root) { if (root == null) return; helper(root.left); count--; if (count == 0) res = root.val; helper(root.right); } }
Problem solution in C++.
class Solution { public: int kthSmallest(TreeNode* root, int k) { // traverse in-order until k-th item is reached std::stack<TreeNode*> st; while (root || !st.empty()) { while (root) { st.push(root); root = root->left; } root = st.top(); if (--k == 0) return root->val; st.pop(); root = root->right; } return -1; } };
Problem solution in C.
int count; int inorder(struct TreeNode* root); int kthSmallest(struct TreeNode* root, int k){ count=k; return inorder(root); //return 4; } int inorder(struct TreeNode* root){ if(root==NULL){ return 0; } int temp1=inorder(root->left); if(temp1!=0) return temp1; count-=1; if(count==0){ return root->val; } int temp2=inorder(root->right); return temp2; }
0 Comments