Binary Trees Traversal Recursive vs. Iterative

Photo reference: https://computersciencewiki.org/index.php/Binary_tree

This neat little trick above saved me a lot of pain and is much quicker to get the traversals. Just think preorder = left, inorder = center, postorder = right. Then weave the string from the top left, to the bottom, to the center, and around until you get to the top right. Wherever the string would 'hook' into a line, write down that number as the next one in that type of traversal.

Given a binary tree, return the inorder traversal of its nodes' values.

Every recursive problem can be done iteratively using a stack. Recursive calls are simply utilizing the call stack that is an inherent part of the programming language. Don't forget to take into account the space the stack/recursive calls take up when doing the O notation for space!

Recursive solution:

public IList InorderTraversal(TreeNode root) 
{
	List result = new List();

	Helper(root, result);
	
	return result;
}

public void Helper(TreeNode root, List result)
{
	if (root == null) return;

	Helper(root.left, result);
	result.Add(root.val);
	Helper(root.right, result);
}

Time: O(n)
Space: O(log n) on average. O(n) worst case if tree is one giant linked list going in one direction.

Iterative solution using a stack:

public IList InorderTraversal(TreeNode root) 
{
	List result = new List();
	Stack stack = new Stack();
	
	TreeNode curr = root;
	
	while(curr != null || stack.Count != 0)
	{
		while(curr != null)
		{
			stack.Push(curr);
			curr = curr.left;
		}
		
		curr = stack.Pop();
		result.Add(curr.val);
		curr = curr.right;
	}
	
	return result;
}

Time: O(n)
Space: O(n)

Read More

Learn C# from Scratch Comprehensive Topic List / How much do I need to know to be a Junior C# Web Dev?

I created a syllabus with a list of what I think a great C# .NET web Junior Developer should know and in what order to study.  I wrote this based on someone with no computer science knowledge, background, training, or schooling and how to get them to go from zero knowledge to a working entry level developer. The list is written in a "checklist format" so you can print this if you like and check-off how much progress you have made and how much is left to go!

I wrote this checklist to help out my mentee with being able to see the "light at the end of the tunnel" and know the scope of what it takes to be a developer.  It can be very difficult to know where to start, how much progress you've made, and the logical next step and this list should assist with that as well as letting you know "how much is enough". 

This list is mainly focused on C# and hits on what topics you should learn for SQL, HTML, CSS, and JavaScript but the details of those are less fleshed out and you should seek out courses online (I listed at those areas to do so).

I believe that if you can learn 60-70% of this list well you could land a C# web developer job. I made the list more comprehensive because leaving off a random 30-40% doesn't make sense to me and some topics are more/less important to certain types of jobs depending on their technology stack.

How I made the syllabus: I broke down C# into Basics Part 1 and Part 2.  Part 1 is basic syntax and everything before classes.  Part 2 is utilizing classes, object oriented programming, and more intermediate C#.  Afterwards I think its good to learn APIs and back-end projects.  Logically next is SQL, databases, and ORMs.  Then front-end technologies.

In the future, I will have a GitHub codebase with projects that go along with this list and in the order of the list, but that is currently in progress and about halfway done. If you would like to follow along, my code is posted here: https://github.com/catenn/LearnCSharp

C# Basics Part 1

Git skills

• Cloning down a new repository using Git Bash
• Differences between Git Pull, Git Fetch, and Git Push and being able to run these commands in Git Bash

Visual Studio Skills

• Using the Solution Explorer
• Creating a brand new solution/project
• Opening an existing solution/project
• Using Git in Team Explorer
• Understanding what the Git Sync button does
• Handling merge conflicts
• Creating a new class file easily
• Adding new projects to an existing solution
• Debugging code
• Be comfortable using Intellisense
• Be comfortable reading Intellisense notes and method signatures

Visual Studio Basic shortcuts:

• Ctrl + X to delete a line
• F5 to run a project
• F10 to step over to the next line
• F11 to step into a method
• Highlighting a selection of code and dragging it to another location
• Shift + Alt + F to fix formatting
• Ctrl + R + R to rename a variable
• Alt-selecting the same thing in multiple rows
• Ctrl + Z to undo (and you can keep hitting this to keep undoing).  Ctrl + Y to redo something you undid (as long as you didn't type more)

C# Types, variables + initialization

• Understand numbers: int, decimal, double, long, ulong, short, uint, byte, etc..
• Understand booleans, boolean logic, using operators like '&&' and '||'
• Understand char
• Understand strings, string interpolation, and string concatenation
• Understand char vs string and single vs double quotes
• Understand what the term "immutable" means and how that relates to a string type
• Learn what a StringBuilder is
• Learn when to use string vs. StringBuilder
• Understand what the keyword "new" does and when to use it
• Define the difference between a reference type and value type
• Understand what 'var' is
• Understand variable initialization
• Understand the scope of a variable based on whether the variable is in a class, method, loop, etc (not talking about access modifiers yet, just understand if a variable is in a class its available anywhere in the class, if its in a method you can use it anywhere in that method after its declared, if its declared in a loop you can only use it there, you may want to initialize something outside of a loop to use in a loop + use it after..).
• Understand when to make local variables and when they are redundant. Understand that you can assign a local variable with the return value of a method. Example var a = TestMethod();

 C# Methods and parameters

• Understand all parts of a method signature
• Understand what a return type is
• Know what it means to return void
• Understand what static is and when to use it
• Understand the difference between arguments and parameters.  You can push an argument into a method as a parameter.
• Understand that when you push a variable into a method, that when the method receives it, it does not have to be called the same name on the other side.  However, naming convention wise it is common to call it the same name. 
• Be able to set a local variable equal to the return value of a method. For example: int result = Add(1 , 2);

if/else and case/switch logic

• Understand if/else if/else logic
• Understand case/switch logic
• Understand inverting if statement, and not having redundant/extra statement
• Understand "!" syntax for "not"
• Understand shorthand syntaxes

Collections: Lists, arrays

• Understand arrays and how they work with types and capacity
• Be comfortable working with lists
• Be comfortable working with a list of lists
• Understand how indexes work with arrays and lists + that they are zero indexed
• Understand when to use an array vs. list and the benefits of each

Loops: for, while, foreach, do

• For loops
• While loops
• Foreach loops
• Do while loops

Basic utility/extension methods

• ToString()
• ToCharArray()
• Trim()
• ToUpper() and ToLower()
• Substring()
• Split()
• ToList() 

Refactoring code practice

C# Basics Part 2

Basics of Classes, properties, methods in classes

• Understand what a class is
• Understand how to use and access properties under a class
• Understand basic {get;set;}
• Understand how to customize {get;set;}
• Basic Inheritance between classes
• Enums

Intermediate C#, Nulls, Regex, and Casting

• Basic uses of LINQ
• Regex
• Dealing with null and checking for null
• Understand what a nullable type is
• Understand how to make something that isn't normally nullable into nullable
• Using Dictionaries (collection type)
• Tuples
• Casting
• Boxing
• Unboxing
• Implicit vs explicit cast

Separating large projects into multiple classes, namespaces, access modifiers

• Understand what a namespace is and how to use them
• Understand what an access modifier is
• Public
• Private
• Internal
• Protected
• Protected Internal
• Private protected
• Sealed
• Understand what the default access modifier is if one isn't listed
• Understand read-only and const
• Understand how access modifiers are related to namespaces
• Understand how access modifiers affect Intellisense
• Understand when/how to use each access modifiers

Class constructors

• What is a constructor?
• What does a constructor do?
• Know that there are different type of constructors available and be able to define them: default, parameterized, copy, static, private
• Class inheritance, interfaces .. Object oriented programming

More complex inheritance between multiple classes / multiple levels of inheritance and base classes

• Interfaces
• Abstract classes
• Interfaces vs. abstract classes
• Inheritance of abstract classes and interfaces
• Overriding inherited methods
• Method overloading
• Method overriding
• Understand what an extension method is, for example the LINQ methods
• Optional parameters

Be able to define the 4 principles of OOP

• Encapsulation
• Inheritance
• Abstracton
• Polymorphism

Design Patterns

• Be able to define SOLID
• Understand that Gang of Four exists / what that is

Unit testing

• Naming convention for project, class files, and method names
• AAA - Arrange, Act, Assert
• Writing a basic unit test for a method
• Writing unit tests to cover a class
• Test attributes
• Running unit tests
• Debugging unit tests
• Code coverage
• Test Driven Development (TDD) and red/green/blue
• What is mocking?
• What is Moq?
• Know there are different frameworks like Nunit, Xunit, and MSTest.

Debugging practice, fix broken code!

Creating a backend API App:

• APIs - what are they, how are they used, etc.
• Get
• Put
• Post
• Patch
• Delete
• How an API project can be accessed by a front end
• How an API project can reach into other layers of logic and get data to a database
• How dev teams can be split into back-end and front end and work out of sync + where the split is in work
• How an API project can be published to Azure and be a live site
• Basic error codes, 404, 500, 200, etc.

API Tools:

• Swagger - know how to use this to test out APIs with the localhost/swagger URL
• Postman - know how to use this to test out APIs
• Fiddler - install this tool, understand how it works

Learn what dependency injection is

• Basic dependency injection and what it is
• Names of frameworks like Unity, Castle Windsor, Autofaq

Debugging practice with tools and full back-end solution

SQL -

• What is a database? What is SQL?  
• Go through: https://sqlzoo.net/ 
• What is a database?
• What is SQL?
• What is NoSQL
• SQL vs NoSQL
• Learn what MongoDB, CosmosDB, Cassandra are and be able to define them only
• Understand basic table structures and how data is broken up into different tables
• Be able to query easily (CRUD operations) SELECT, INSERT, UPDATE, DELETE, etc.
• T-SQL
• Stored Procedures
• Joins
• Keys
• Foreign Keys
• Triggers
• Know what ACID is

SQL Server Management Studio (SSMS) basics

• Be able to login to a local SQL Server
• Be able to login to an Azure SQL Server
• Be able to find databases, tables easily
• Be able to edit tables manually in SSMS
• Feel comfortable using SSMS as a tool
• Understand difference between SSMS and the DB itself
• Understand the difference between local vs. Azure IaaS vs. Azure PaaS SQL
• How to connect web app to SQL, ORMs

What is an ORM?

• What does an ORM do?
• ADO.NET
• Dapper - learn what this is and what is can do
• Entity Framework - learn what this is and what is can do

Javascript -

• Basic JavaScript syntax and logic
• Take online course on JS like CodeSchool.com or CodeAcademy.com
• Know what jQuery is and what it is for
• Know what AJAX is and what it is for
• Know what React JS and Angular JS are and very basics of these / compare and contrast these two frameworks
• Know what Vue.JS is
• Browser debugger
• Be comfortable using the debuggers in each browser: Chrome, Firefox, and Edge

HTML/CSS

• Take a HTML and CSS online course
• Know how to make a basic HTML5 page with divs or tables
• Know all basic HTML elements
• New HTML5 elements
• Good practices with CSS and how to use periods and spaces to chain CSS
• When to and not to use "important" css styling with "!"
• Twitter Bootstrap framework and use of it
• SASS
• Know what bundling is

End to End - Debugging

• Reading and understanding stacktraces
• How to use try/catch, setup exceptions
• Exceptions
• Error checking
• Throw/Catch errors
• How to determine if bug is in front end, backend, or DB issue. Be able to explain this on an interview.

Agile/Scrum/Devops Basics

• Understand how requirements can be broken into Epics/Features/User Stories
• Understand what a User Story / Product Backlog Item is
• Be able to read a business requirement and break it into technical steps that you can estimate in hours.
• Understand how to estimate your work in hours (always over-estimate!)
• Know what Agile is
• Know what a Kanban workflow is
• Know what a Sprint is.. understand sprint planning, stand-up, sprint review, sprint retrospective meetings and their purposes
• Understand what the following roles do: Product Owner, Business Analyst, Scrum Master, Quality Assurance, and how you work with these roles at work. 

Advanced topics / Optional / Nice to know topics

• Understand what the cloud is and what Azure, AWS, and Google Cloud are.  Understand the difference between cloud and on-premise offerings.  Understand the terms SaaS, IaaS, and PaaS in relation to cloud services. 
• UML Diagrams
• Recursive functions / recursion
• C# Dynamics
• Binary operators
• Knowing binary
• Compile time vs Runtime
• Structs
• Delegates
• DevOps CI/CD
• Git Branching, switch branches, branching strategies, overall release strategy
• Angular / React JS
• Design Patterns/Architecture
• Stack/Heap
• Runtime, JIT, etc
• Pointers
• Basic Networking

Read More