The Leetcode July Challenge Day 2 problem asks us to take a binary tree, given as a root node pointer, and return a list of values representing a bottom-up level order traversal. So, we want to do something along these lines:

Input:

graph TD; 1((1)) --- 2((2)) 1((1)) --- 3((3)) 2((2)) --- 4((4)) 2((2)) --- 5((5)) 3((3)) --- 6((6)) 3((3)) --- 7((7))

Output: [[4,5,6,7],[2,3],[1]]

Anytime I’m working with a binary tree, I start by asking myself if the expected output pattern matches, or is similar to, any common traversal–preorder, inorder, postorder–or a search pattern–depth-first or breadth-first search. From the problem visualization, it looks a lot like a breadth-first search where nodes are arranged by their distance from the root, just in reverse. This is a small twist on a pretty typical problem, but it’s a great chance to make sure we have a polished algorithm. I’ll look at both a recursive and an iterative algorithm for this problem, both of which have an asymptotic complexity of O(n). The key to either of these approaches is the ability keep track of what level the current node belongs to. In recusion this is achieved by passing an integer argument down the recusion chain which increments when passing from parent to child nodes. In the iterative approach, each level is processed in order, and the notable value is the width of the current level. Luckily, the queue at the beginning of any given iteration contains all of the nodes for the current level, so we know how many nodes to take from the queue for that level. But, to the point, let’s look at the code! A recursive solution:

vector<vector<int>> levelOrderBottom(TreeNode *root) {
	vector<vector<int>> levelOrderValues;
	levelOrderBottom(root, levelOrderValues, 0);

	reverse(levelOrderValues.begin(), levelOrderValues.end());
	return levelOrderValues;
}
void levelOrderBottom(TreeNode* root, vector<vector<int>>& levelOrderValues, int level) {
	if (root == NULL) return;
	// Trigger a new output level.
	if(level == levelOrderValues.size()) levelOrderValues.push_back({});

	levelOrderValues[level].push_back(root->val);

	levelOrderBottom(root->left, levelOrderValues, level + 1);
	levelOrderBottom(root->right, levelOrderValues, level + 1);
}

That’s a pretty straightforward approach with the only tricky part is remebering to set a condition to create a new subarray of node values if the current node’s level hasn’t been added yet. While the recursive implementation is sufficient, I always lean towards iterative implementations when feasible, as I find them easier both to write and debug. Let’s take a look at mine:

vector<vector<int>> levelOrderBottom(TreeNode* root) {
	// check for an early return.
	if(!root) return {};
	if(!root->left && !root->right) return {{root->val}};

	vector<vector<int>> levelOrderValues;

	queue<TreeNode*> nodeQueue;
	nodeQueue.push(root);
	while(!nodeQueue.empty()) {
	  vector<int> level;
	  int levelWidth = nodeQueue.size();
	  for(int i=0;i<levelWidth;i++) {
		 TreeNode* current = nodeQueue.front();
		 nodeQueue.pop();
		 level.push_back(current->val);
		 if(current->left) q.push(current->left);
		 if(current->right) q.push(current->right);
	  }
	  levelOrderValues.push_back(level);
	}
	reverse(levelOrderValues.begin(), levelOrderValues.end());
	return levelOrderValues;
}

Note: There’s another linear time algorithm, Morris Traversal, worth looking into if you need a solution optimized for both time and memory use, but requires some error-prone pointer work, which I will leave off for now. That’s another fun problem done! Check back tomorrow for another interesting look.