Iterative solution for Leetcode Problem 114

Leetcode-Problem-114.js

//Iterative solution for Leetcode Problem 114.
//Currently having out of memory issues on Leetcode, but runs flawlessly on local Node setup
var flatten = function(root) {

	if(root === null) return null;

	const DOWN = 1; //represents performing a recursive function call
	const UP = 2;   //represents returning from a recursive function call

	let stack = [];
	let traversalState = DOWN;
	let tail = null;

	stack.push(root)

	while(stack.length > 0) {

		let node = stack[stack.length - 1];

        //we found a leaf node
		if(node.left === null && node.right === null) {
			traversalState = UP;    //effectively we are "returning" after finding the leftmost node
			tail = stack.pop();
			continue;
		}

        //keep traversing down the tree until we find a leaf node
		if(traversalState == DOWN) {
			if(node.left) {
				stack.push(node.left)
			} else if(node.right) {
				stack.push(node.right)
			}
		}

        //we have "returned" from the recursive call. Time to re-wire the nodes
		if(traversalState === UP) {
			if(tail) {

				let node2 = stack.pop()

				tail.right = node2.right;
				node2.right = node2.left;
				node2.left = null;

				if(tail.right) {
					stack.push(tail.right)
					traversalState = DOWN;
				}
			}
		}
        
	}
   
}