# Java/Python one-pass in-order traverse from the right

• Using in-order traverse from the right, just 1 pass needed.

Java:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {

int sum = 0;

public TreeNode convertBST(TreeNode root) {
if (root != null) traverse(root);
return root;
}

public void traverse(TreeNode root){
if (root.right != null) traverse(root.right);
int temp = root.val;
root.val += sum;
sum += temp;
if (root.left != null) traverse(root.left);
}
}
``````

Python:

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.sum = 0
if root: self.traverse(root)
return root

def traverse(self, root):
if root.right:
self.traverse(root.right)
temp = root.val
root.val += self.sum
self.sum += temp
if root.left:
self.traverse(root.left)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.