Iterative traversal in C - gives run time error

  • 0

    I am attempting to implement the iterative solution for post order traversal, with one stack. The postorderTraversal() procedure below, gave expected results for sample trees I tried, but for a much complicated tree in OJ it threw run time error - The failed input was :


    I would really appreciate if someone could give me some tips on debugging this issue:

    1. How can the exact tree above be created as input to the program, to debug it locally - is the above a BreadthFirst node listing of the tree - or a PostOrderDepthFirst listng ?
    2. I tried to go through the execution of the procedure with pen and paper for upto a 6 level tree - I could not point out the the issue with the logic below - is there any major flaw in the logic that any of you can point out?

    Thanks a lot in advance, for your time and any tips you can provide. My apparently buggy code below :

    // post order iterative
    #define STACK_SZ 300
    #define MAX_RET_SZ 500
    typedef struct stack {
    	int size;
    	int top;
    	struct TreeNode** arr;
    struct stack tree_stack;
    #define Init_Stack(stackArr, sz) tree_stack.arr = stackArr; tree_stack.size = sz; = -1;
    #define Empty_Stack (( == -1)? 1:0) 
    int Push_Stack(struct TreeNode* node) {
    	if( == STACK_SZ-1)
    		return 0;;
    	tree_stack.arr[] = node;	
    	printf("push %d\n", node->val);
    struct TreeNode* Pop_Stack() {
    	struct TreeNode* node;
    	if( == -1)
    		return NULL;
    	node = tree_stack.arr[];;
    	printf("pop %d\n", node->val);
    	return node;
    int* postorderTraversal(struct TreeNode* root, int* returnSize) {	
    	int *ret_arr = malloc(MAX_RET_SZ);
    	int  ret_arr_idx = 0;
    	struct TreeNode** stackArr = (struct TreeNode**)malloc(STACK_SZ*4);	
    	struct TreeNode *cur_node, *new_node;
    	Init_Stack(stackArr, STACK_SZ);    	
        cur_node = root;
    	while(cur_node) {
    		// if leaf then visit the node
    		if(cur_node->left == NULL && cur_node->right == NULL){
    			ret_arr[ret_arr_idx++] = cur_node->val;
    		// otherwise push the node and push its right child
    		else {
    			if(cur_node->right != NULL) Push_Stack(cur_node->right);
    			cur_node = cur_node->left;
    			// repeat till we hit a leaf
    			if(cur_node) continue;
    		// we just visited a leaf, so pop one node from stack
                // which will be right child of the parent 
                // or if no right child present then the parent itself
    		while(!Empty_Stack) {
    			//if cur node is, new node's left child and new node has no right child OR
    			//   cur node is new node's right child
    			// then visit new node
    			if((new_node->left == cur_node && new_node->right == NULL) || new_node->right == cur_node) {
    				ret_arr[ret_arr_idx++] = new_node->val;
    				// update cur node 
    				cur_node = new_node;
    			// otherwise break off the stack pop loop 
    			// and then push back the node 
    			else {
    				cur_node = new_node;
    	if(Empty_Stack) break;
    	*returnSize = ret_arr_idx;
    	return ret_arr;

Log in to reply

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