I am writing a simple function for inorder traversal of a tree. The function looks like this:
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root,typ, par) {
let result = [] ;
console.log(`side = ${typ} currentVal = ${root? root.val: 'no root'}`,root)
if (!root) return []
left = inorderTraversal(root.left, 'left', root.val)
right = inorderTraversal(root.right, 'right', root.val )
console.log(`side = ${typ} currentVal = ${root? root.val: 'no root'} parent = ${par}`,root)
console.log(`${root.val}-left, and parent= ${par}`, left)
console.log(`${root.val}-rigth, and parent= ${par}`, right)
result = [...left, root.val, ...right ];
console.log('res', result)
return result
};
Note: The brnch(represents the side I am traversing i.e left/right) and par(parent's value), are just parameters I pass for debugging purposes.
The problem or challenge I am working on can be found here: https://leetcode.com/problems/binary-tree-inorder-traversal/submissions/
The function recursively traverses through a tree and when the left and right sides are determined, it uses the spread operator to combine them.
My console.logs output are:
side = undefined currentVal = 1 [1,null,2,3]
side = left currentVal = no root null
side = right currentVal = 2 [2,3]
side = left currentVal = 3 [3]
side = left currentVal = no root null
side = right currentVal = no root null
side = left currentVal = 3 parent = 2 [3]
3-left, and parent= 2 []
3-rigth, and parent= 2 []
res [ 3 ]
side = right currentVal = no root null
side = right currentVal = 2 parent = 1 [2,3]
2-left, and parent= 1 [ 3 ]
2-rigth, and parent= 1 []
res [ 3, 2 ]
side = undefined currentVal = 1 parent = undefined [1,null,2,3]
1-left, and parent= undefined [ 3 ]
1-rigth, and parent= undefined [ 3, 2 ]
res [ 3, 1, 3, 2 ]
my input is [1,null,2,3]. the expected output is [1,3,2] and the current/actual result is [3,1,3,2]
If you look at the logs(specifically the last 3 lines), you'll see when the function bubbles back up to when root val is 1, the left is [3], right is [3,2]. If the left wasn't [3] then I would get the correct result with [left, root.val, right]. Can someone explain why is left returning [3]? I think it should be []. In a similar sub-problem where root.val is 2 and the right leaf is null, I get right = []. I don't know why left is [3].
I don't need a solution for inorder traversal but rather answer to why left is returning [3]. In addition, when I change the order of when operations are performed, the problem is resolved. code :
var inorderTraversal = function(root,typ, par) {
let result = [] ;
console.log(`side = ${typ} currentVal = ${root? root.val: 'no root'}`,root)
if (!root) return []
left = inorderTraversal(root.left, 'left', root.val)
//modifying result before traversing right
result = [...left, root.val]
right = inorderTraversal(root.right, 'right', root.val )
console.log(`side = ${typ} currentVal = ${root? root.val: 'no root'} parent = ${par}`,root)
console.log(`${root.val}-left, and parent= ${par}`, left)
console.log(`${root.val}-rigth, and parent= ${par}`, right)
result = [...result, ...right ];
console.log('res', result)
return result
};
This resolves the issue even though the left is still [3], can someone please help with why this happens?
Your scope is interfering with the value that you get, try restricting the scope of left and right variables to local using let.
var inorderTraversal = function(root) {
let result = [] ;
if (!root) return []
let left = inorderTraversal(root.left, 'left', root.val)
let right = inorderTraversal(root.right, 'right', root.val )
result = [...left, root.val , ...right ];
return result
};