<prompt> Kwa kuzingatia mzizi wa mti wa utafutaji wa binary, na nambari kamili k, hurejesha _the_ kth _thamani ndogo zaidi 1-indexed ya thamani zote za nodi katika mti_.Mfano wa 1:Ingizo: mzizi 3,1,4,null,2, k 1Pato: 1Mfano wa 2:Ingizo: mzizi 5,3,6,2,4,null,null,1, k 3Pato: 3Vikwazo: Idadi ya nodi kwenye mti ni n. 1 k n 104 0 Node.val 104Fuata: Ikiwa BST inarekebishwa mara kwa mara yaani, tunaweza kuingiza na kufuta shughuli na unahitaji kupata kth ndogo zaidi mara kwa mara, unaweza kuboresha vipi?  <response>: chatudarasa TreeNode: def __init__binafsi, val0, leftNone, rightNone: self.val val self.left kushoto self.right hakidef kthSmallestmizizi, k: stk curr mzizi wakati Kweli: huku curr: stk.appendcurr curr curr.left curr stk.pop k - 1 ikiwa k 0: kurudi curr.val curr curr.rightmaelezoKanuni hutumia mbinu ya kurudia kutekeleza uteuzi wa utaratibu wa mti wa utafutaji wa binary BST. Tunatumia stack kufuatilia nodi zilizotembelewa. Kuanzia na node ya mizizi, tunapitia chini ya kushoto hadi tufikie node ya kushoto, kusukuma kila nodi kwenye stack njiani.Tunapofikia nodi isiyofaa, tunapiga sehemu ya juu ya stack nodi ya kushoto kabisa. Node hii itakuwa thamani ndogo zaidi kwenye mti. Tunaendelea kuvuka miti midogo ya kulia, tukipunguza thamani ya k kila wakati tunapoibua nodi kutoka kwa rafu. Wakati k inakuwa 0, tunarudi thamani ya node ya sasa - hii ni kipengele cha kth ndogo zaidi.Tunarudia traversal mpaka kipengele cha kth kinachohitajika kinapatikana. Utata wa wakati ni OH k ambapo H ni urefu wa mti. 